题目描述

一只松鼠站在一棵长满橡子的树根处，准备收集橡子。

这棵树有 $N$ 个分叉点和 $N-1$ 条树枝，每个分叉点编号为 $1$ 到 $N$，其中 $1$ 号点是树根。每个分叉点都有一个橡子。

松鼠一开始在根节点，并且已经拿走了根节点的橡子。接下来，它需要选择一串树枝进行移动，使得每个分叉点被访问的次数恰好等于与它相连的树枝数量。每当松鼠第一次访问某个分叉点时，就会拿走这个分叉点上的橡子。

松鼠有 $M$ 个要求。第 $i$ 个要求为 $(a_i,b_i)$，表示 $a_i$ 号分叉点的橡子必须在 $b_i$ 号分叉点的橡子之前被拿走。

请计算满足所有要求的不同移动方式数量，答案对 $10^9+7$ 取模。

输入格式

第一行输入两个整数 $N,M$。

接下来 $N-1$ 行，每行输入两个不同整数 $u_i,v_i$，表示一条树枝。

接下来 $M$ 行，每行输入两个不同整数 $a_i,b_i$，表示一个先后顺序要求。

输出格式

输出一个整数，表示满足全部要求的移动方式数量对 $10^9+7$ 取模的结果。

数据范围

• $2\le N\le 100000$
• $1\le M\le 300000$
• $1\le a_i,b_i,u_i,v_i\le N$
• $D\le 12$，其中 $D$ 为一个分叉点连接的树枝最大数量。

子任务

样例 1

输入

3 2
1 2
1 3
1 2
3 1

输出

0

样例 2

输入

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

输出

3