403355: GYM101138 C Stickmen

Limak is a little bear who loves to play with graphs. Recently, he defined a new structure in a graph and called it a stickman.

A stickman is a set of 7 different vertices and 6 edges. Vertices should be connected by edges as in the image below.

You can see here two legs, two arms and a head. Formally, one vertex (the one between arms) must be connected to four other vertices and one of these four must be connected to two more vertices.

Limak has an undirected graph with n vertices and m edges, without loops and multiple edges. He asks you a favor. Could you count how many stickmen there are in Limak's graph, modulo 10⁹ + 7?

A stickman is defined by a set of 7 vertices and 6 edges. Two stickmen are different if and only if the set of vertices isn't the same or the set of edges isn't the same. The order of vertices or edges doesn't matter (so you shouldn't distinguish legs for example).

The first line of the input contains two integers n and m (7 ≤ n ≤ 200, ) — the number of vertices and the number of edges. Vertices are numbered 1 through n.

Each of the next m lines contains two integers a_i and b_i (1 ≤ a_i, b_i, a_i ≠ b_i) — indices of two vertices connected with an edge. Any unordered pair of vertices will appear at most once.

Print the number of stickmen in the given graph, modulo 10⁹ + 7.

7 8
1 2
1 3
1 4
1 5
1 6
5 6
7 5
7 6

2

There are two different stickmen in the sample, showed in the drawing below. Since there are only 7 vertices in the graph, the set of vertices of each stickman must contain all vertices. The two stickmen don't have the same set of edges though and this is why they are different at all.