Given an undirected connected graph of vertices and edges, where is guaranteed to be odd. You want to divide all the edges to groups under following constraints:

• There are exactly 2 edges in each group
• The 2 edges in the same group share a common vertex

Determine the number of valid dividing schemes modulo . Two schemes are considered different if there are 2 edges that are in the same group in one scheme but not in the same group in the other scheme.

The first line contains one integer , denoting the number of vertices.

Following  lines each contains two integers , denoting that vertex  are undirectedly connected by an edge.

It is guaranteed that  is odd and that the given graph is connected.

Output one line containing one integer, denoting the number of valid dividing schemes modulo .

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

3

The 3 schemes are:
    The 3 edge groups are 
    The 3 edge groups are 
    The 3 edge groups are