Yua and the Gomduri Car

To celebrate the new year, Yua bought a V.Nets self-driving car. Yua plans to drive the new car to the sea and eat plenty of raw fish (Yua follows the government's quarantine guidelines for disease prevention). While driving on the highway, Yua could not help but be stunned. V.Nets's self-driving system was terrible. Feeling deeply betrayed by V.Nets, Yua resolved to design a self-driving car personally.

The Gomduri car is the self-driving car Yua designed. The Gomduri car always moves from its current vertex to an arbitrary adjacent vertex. Yua believes that if a path from the start to the destination exists and time is unlimited, the Gomduri car can always reach the destination. Yua suddenly became curious: given a graph, how many paths can the Gomduri car travel?

But Yua could not solve this problem. To lower the difficulty, Yua allowed revisiting the same vertex or edge along a path.

Given a graph, write a program that counts the paths of length 7 that the Gomduri car can travel. The Gomduri car may pass through the same vertex or edge multiple times.

The first line gives the number of vertices $N$ and the number of edges $M$.

The following $M$ lines give the numbers $u, v$ of the two vertices that each edge connects.

The given edges are undirected, and all input is separated by spaces.

On the first line, print the number of paths of length 7 that the Gomduri car can travel. Since the answer can be very large, print it modulo $10^9 + 7$.

• $2 \le N \le 100,000$
• $1 \le M \le \min(N \times (N - 1) / 2, 100,000)$
• $1 \le u, v \le N$
• $u \ne v$
• The given graph contains no duplicate edges.

Since the input is large, using fast input is recommended.

The length of a path is the number of edges that make up the path.