Byteland has cities (numbered from to ) and bidirectional roads. A path is comprised of or more connected roads. It is guaranteed that there is a path from any city to any other city.
Steven is a road maintenance worker in Byteland. He is required to maintain exactly paths on any given workday. He cannot work on the same road twice in one day (so no paths can contain the same roads). Steven can start his workday in any city and, once he has finished maintaining a path, teleport to his next starting city.
Given , help Steven determine how many different possible path sets will allow him to perform his maintenance duties. Then print the answer modulo .
Input Format
The first line contains space-separated integers, (the number of cities) and (the number of roads to maintain).
Each line of the subsequent lines contains space-separated integers, , describing a bidirectional road between cities and .
Constraints
Output Format
Find the number of different path sets that will allow Steven to complete orders, and print the answer .
Sample Input
4 2
1 2
2 3
2 4
Sample Output
6
Explanation
For the following Byteland map:
Steven can maintain roads using any of the following routes:
- and
- and
- and
- and
- and
- and
Thus, we print the result of on a new line, which is .