Cycle with Two Leaves

Time limit4sMemory limit1024 MB

Summary

Count subgraphs formed by a 4-cycle plus two pendant edges attached to the same cycle vertex, modulo 1e9+7.

Level: Hard8 of 10
Topics: Graph, Combinatorics, Math
Solved: No attempts yet

Problem

You are given an undirected simple graph $G$ . Count the number of subgraphs with the following shape.

Four distinct vertices form one 4-cycle.
Two other distinct vertices are attached as leaves to the same vertex of that 4-cycle.

Equivalently, the target graph consists of one 4-cycle and two pendant edges incident to the same cycle vertex. Two subgraphs are considered different only when their selected edge sets are different. Extra edges in the original graph that are not selected do not matter. Print the answer modulo $10^9+7$ .

Input

The first line contains the number of vertices $N$ and the number of edges $M$ of $G$ . $(1 \le N, M \le 239000)$

Each of the next $M$ lines contains two vertex numbers $x$ and $y$ joined by an edge. $(1 \le x, y \le N)$

The graph is simple, and the vertices are numbered from $1$ to $N$ .

Output

Print the number of subgraphs satisfying the condition, modulo $10^9+7$ .

Examples1

Example 1
Input
```
8 8
1 3
2 3
3 4
3 5
4 6
5 6
6 7
6 8
```
Expected output
```
2
```