The mad genius Dr. Shpuntik is assembling an army of robotic "hedgehogs" out of scrap metal. Before him lies a massive iron structure consisting of $$$n$$$ circular components (gears) connected by $$$m$$$ steel rods (each rod connects exactly two components). To activate a single robotic hedgehog, the doctor must select one component and a subset of the steel rods attached to it — these will serve as the "spines." For a robotic hedgehog to be considered valid and ready for operation, it must have at least three spines.
Shpuntik dislikes monotony, so every robot he creates must be unique. Two robotic hedgehogs are considered distinct if they are based on different components, or if they have different sets of spines (i.e., the sets of rods chosen from the same component are not identical). The doctor wants to determine the total number of distinct, valid robotic hedgehogs that can be formed from his structure. There are so many potential hedgehogs that Shpuntik cannot manage the count on his own. Since the number of robots can be extremely large, please output the answer modulo $$$10^9 + 7$$$.
Formally: you are given an undirected graph. You need to calculate the number of subgraphs that take the form of a "hedgehog" — a structure consisting of a central vertex connected by edges to at least three other vertices, with no additional edges included. Note that while the vertices at the ends of the "spines" might be connected to each other in the original graph, these connections are not included when defining the "hedgehog" subgraph. Two "hedgehogs" are considered distinct if there is at least one vertex present in one that is not present in the other. You need to calculate the remainder when the number of "hedgehogs" is divided by $$$10^9 + 7.$$$
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$n - 1 \le m \le 3 \cdot 10^5$$$), representing the number of components and the number of rods in the structure, respectively. The following $$$m$$$ lines contain descriptions of the rods. Each line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$), representing the endpoints of a rod. It is guaranteed that the structure is connected and that no rod description is repeated.
Output a single integer — the number of distinct hedgehog-robots in the given construction, modulo $$$10^9 + 7$$$ (i.e., the remainder when divided by $$$10^9 + 7$$$).
Subtask 1 (up to 20 points): $$$n, m \le 15$$$
Subtask 2 (up to 24 points): $$$n, m \le 2000$$$
Subtask 3 (up to 56 points): $$$n, m \le 3 \cdot 10^5$$$
4 31 21 31 4
1
5 41 21 31 41 5
5
A note on the Python language: two numbers separated by a space can be read as follows:
n, m = map(int, input().split())