题目描述

城市 $B$ 最近被评为国家级旅游胜地，于是它决定把城市中的某些区域指定为文化中心。

城市由 $N$ 个路口组成，编号为 $1$ 到 $N$。这些路口之间有 $N-1$ 条道路，保证任意两个路口之间都可以通过若干条道路直接或间接到达。因此，整座城市形成一棵树。

每个路口都有一个文化价值，路口 $i$ 的文化价值为 $v_i$。

城市可以把一个路口集合 $S$ 指定为文化中心，当且仅当集合 $S$ 是连通的：从 $S$ 中任意一个路口出发，到达 $S$ 中任意另一个路口时，可以只经过 $S$ 中的路口和道路。

设 $\mathcal M$ 为所有可以被指定为文化中心的路口集合。

对于任意 $S\in\mathcal M$，它的文化中心价值定义为：

$$val(S)=\left(\sum_{x\in S}v_x\right)^P$$

其中 $P$ 是一个给定常数。

城市会把 $\mathcal M$ 中的每一个集合都指定为一次文化中心，每次持续一天，顺序任意。市政府想知道所有这些文化中心价值之和，即：

$$\left(\sum_{S\in\mathcal M} val(S)\right)\bmod (10^9+7)$$

请你求出这个值。

输入格式

第一行两个整数 $N,P$。

第二行 $N$ 个整数：

$$v_1,v_2,\ldots,v_N$$

第三行 $N-1$ 个整数：

$$p_2,p_3,\ldots,p_N$$

对于每个 $2\le i\le N$，表示路口 $i$ 与路口 $p_i$ 之间有一条道路。

保证 $p_i<i$。

输出格式

输出一行一个整数，表示答案。

约束与说明

模数为：

$$10^9+7$$

子任务

子任务	分值	限制
1	7	$1\le N\le 15$，$1\le v_i\le 10^9$，$1\le P\le 7$
2	12	$1\le N\le 100$，$v_1=v_2=\cdots=v_N=1$，$1\le P\le 7$
3	5	$1\le N\le 1000$，$v_1=v_2=\cdots=v_N=1$，$1\le P\le 7$
4	8	$1\le N\le 1000$，$1\le v_i\le 10^9$，$P=1$
5	10	$1\le N\le 100000$，$1\le v_i\le 10^9$，$P=1$
6	9	$1\le N\le 1000$，$1\le v_i\le 10^9$，$P=2$
7	13	$1\le N\le 100000$，$1\le v_i\le 10^9$，$P=2$
8	14	$1\le N\le 100000$，$1\le v_i\le 10^9$，$1\le P\le 7$，每个路口至多是两条道路的端点
9	22	$1\le N\le 100000$，$1\le v_i\le 10^9$，$1\le P\le 7$

样例 1

输入

3 2
1 2 3
1 1

输出

75

样例 2

输入

4 1
9 10 9 10
1 2 1

输出

190

样例 3

输入

5 2
1 2 3 4 5
1 1 3 3

输出

1133

样例 4

输入

7 2
1 1 1 1 1 1 1
1 1 1 2 5 2

输出

590

样例 5

输入

10 3
13 8 4 8 6 13 6 8 14 9
1 2 3 3 2 6 5 4 8

输出

12312296

样例解释

对于样例 1，边为 $(1,2),(1,3)$。

所有连通点集为：

$$\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{1,2,3\}$$

它们的点权和分别为：

$$1,2,3,3,4,6$$

平方后得到：

$$1,4,9,9,16,36$$

总和为 $75$。