题目描述

在某个疯狂星期四，粉兔的KFC人满为患。KFC的桌子形如一棵$n$个点的树，标号从$1$到$n$，现在出了$n$个餐但是没人取。标号为$i$的点放着编号为$p_i$的打包袋，$p_1,p_2,\cdots,p_n$是一个排列。

粉兔可以选择两个相邻的点，如果这两个点放的打包袋也相邻（即编号的差绝对值为$1$），粉兔可以交换这两个打包袋。

粉兔可以交换无数次打包袋。粉兔想知道，它可以把KFC的餐品变成多少种可能的情况？

答案可能很大，所以你只需要输出答案对$1000000007$取模的结果。

输入格式

第一行包含一个整数 $n$，表示kfc的点数。

接下来$n-1$行，每行两个整数，给出树的一条边。

接下来$n$个数$p_1,p_2,\cdots,p_n$。

输出格式

输出一个整数表示答案$\bmod 1000000007$。

样例

Input

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

Output

7

Hint

如图所示，三张图分别代表了4、2、1种情况。

数据范围

对于所有数据，$n\le 500000$。

测试点1. $n\leq 10$。

测试点2-3. 树是一条链，$i$到$i+1$有一条边，$\forall i\in[1,n-1]$。

测试点4-6. $n\le 500$。

测试点7-10. 无特殊限制。