Walk Alone has a binary tree with nodes labelled from to rooted at node . Each node in the tree has at most two children, the left child and the right child , where denotes the label of the left child and if does not have a left child, and similarly. We omit the subscript if is clear from the context. The right child of exists only if has a left child.
He once performed an operation named left-child right-sibling (LCRS) transform on the tree for exactly times. In each operation, he would

• Visit all vertices in descending order of depth. For each vertex with two children and , remove edge and let the right child of be . It can be shown that does not have a right child at this time.

• For each vertex with a right child and no left child, i.e., and , swap and .

You can refer to the following code for better understanding.

void dfs(int u) {
  // l[u]/r[u]: The left/right child of node u
  // Recursively visit all children of node u
  if (l[u] != 0) dfs(l[u]);
  if (r[u] != 0) dfs(r[u]);

  if (r[u] != 0) {
    // Here l[u] != 0 because r[u] != 0
    if (l[l[u]] == 0) l[l[u]] = r[u];
    else r[l[u]] = r[u];
    r[u] = 0;
  }
}
void LCRS() {
  dfs(1);
}

However, he forgot what the original tree is like. Now he wants you to tell him the number of different possible initial trees modulo . Two trees and are considered different if and only if there exists a node such that .

The first line contains two integers  and , the number of nodes and the number of operations Walk Alone has done, respectively.
The -th of the next  lines contains two integers  and , indicating that the left and right child of  in the resulting tree are  and  respectively. If  has no left (right) child, then . It is guaranteed that the given graph is a tree rooted at node , and that  only if .

Output an integer indicating the number of possible initial trees modulo .

5 1
2 0
4 3
0 0
5 0
0 0

2

4 2
2 0
3 0
4 0
0 0

4

4 2
2 0
3 4
0 0
0 0

0

In the first example, the two possible trees are illustrated as below.