Country A and Country B are at war, and Country A intends to build some facilities.
The territory of country A is composed of cities, and two-way roads connect these cities, so that any two cities can be directly or indirectly reached by road. Country A intends to choose one or more cities (at least one) and build a facility at each of these cities.
Communications between facilities are very important. However, country B will likely attack a road of country A in the near future, but the specific target of the attack is unknown. If this attack is successful, this road will be cut off, which may cause two facilities in country A to be unable to reach each other, which country A tries to avoid. Therefore, country A decides to send troops to guard several roads (it can be one or more, or none of them). Country A is confident that the roads guarded by troops can resist the attack of country B and not be cut off.
Country A hopes to formulate a plan for building facilities and guarding roads, so that no matter which road of country A is attacked by country B, all facilities will remain reachable from each other. Now, please help country A calculate the total number of possible plans for building facilities and guarding roads. Since the number of schemes may be large, you only need to output its value modulo . Two proposals are considered different if and only if there exists at least one city that has a facility built in one proposal but not in the other, or at least one road that is guarded by troops in one proposal but not in the other.
Input Specification
The first line contains two positive integers and , which represent the number of cities and the number of two-way roads, respectively.
The next lines each containing two positive integers , , describing a two-way road connecting cities and . It is guaranteed that there are no multiple edges or self-loops.
Output Specification
The output should contain one integer, representing the number of ways to build facilities and assign troops to roads, modulo .
Sample Input 1
2 1
1 2
Sample Output 1
5
Explanation of Sample 1
Country A has two cities, and a road connects them. All possible scenarios are as follows:
- Build a facility in city 1, do not guard the road;
- Build a facility in city 1, guard the road;
- Build a facility in city 2, do not guard the road;
- Build a facility in city 2, guard the road;
- Build facilities in both cities 1 and 2, guard the road.
Sample Input 2
4 4
1 2
2 3
3 1
1 4
Sample Output 2
184
Additional Samples
Additional sample cases can be found here.
Constraints
For all data, it is guaranteed that , , , .
Case | Special Condition | ||
---|---|---|---|
none | |||
and road connects to | |||
none |
Comments