题目描述

用 $0$ 代表空树，如果一个节点没有左子树，那么认为它的左子树是空树（右子树同理）。对任意二叉树 $A$，$0\le A$ 成立； 对任意非空二叉树 $A$，$A\le0$ 不成立。用 $\text{ls}$ 代表左子树，$\text{rs}$ 代表右子树，则对于非空二叉树 $A,B$，$A\le B$ 当且仅当 $\text{ls}(A)\le\text{ls}(B)$ 且 $\text{rs}(B)\le\text{rs}(A)$。$A=B$ 当且仅当 $A\le B$ 且 $B\le A$。否则 $A\not=B$。

给定节点编号为 $1$ ~ $n$ 的二叉树 $A$。$B$ 的初始值为 $A$。对 $B$ 重复进行以下操作：任选 $B$ 的一个儿子数量不超过 $1$ 的节点，为这个节点增加一个儿子（使得 $B$ 仍然是二叉树）。左右有区别。

问共有多少不同（定义见上文）的 $B$ 满足 $B$ 的节点数为 $n+m$ 且 $A\le B$。

输入格式

第一行是两个整数 $n,m$。

接下来 $n$ 行，给出二叉树 $A$。第 $i+1$ 行有两个整数，第一个是 $i$ 号节点的左儿子编号，第二个是右儿子编号（如果没有左儿子/右儿子，用 $0$ 代替）。

输出格式

一个整数，表示满足条件的 $B$ 的数量，对 $1914270647$（一个质数）取模。

样例一

input

4 2
2 0
3 0
0 4
0 0

output

5

explanation

样例二

input

6 3
0 0
0 3
6 4
0 1
2 0
0 0

output

48

样例三

input

1 1427
0 0

output

1224214018

数据范围

所有数据满足 $1\le n,m\le10^6$。