秋之国共有$$$n$$$个城市,编号从$$$1$$$到$$$n$$$。人们可以使用 $$$n-1$$$ 双向道路在任意两个城市之间旅行。
今年,政府决定分离王国。将会有不同级别的区域。整个王国将是$$$1$$$级别的区域。 $$$i$$$-th 级别的每个区域应分为多个(至少两个)$$$i+1$$$-th 级别区域,除非 $$$i$$$-th 级别是最后一个级别。每个城市应该属于每个级别的一个区域,并且对于同一区域中的任意两个城市,应该可以仅通过同一区域中的城市在它们之间旅行。
根据研究,对于每个城市$$$i$$$,都有一个值$$$a_i$$$,描述了这个城市的重要性。同一级别的所有区域的城市重要性总和应相等。
你的任务是找出有多少个计划来确定满足所有条件的区域的分离。当且仅当两个规划的级别数不同,或者一个规划中一个级别的同一区域存在两个城市,而另一个规划中该级别的不同区域存在两个城市时,两个规划才被视为不同。由于答案可能非常大,因此输出它对 $$$10^9+7$$$ 取模。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — 城市的数量。
第二行包含 $$$n$$$ 整数,其中第 $$$i$$$ 是 $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — 每个城市的值。
第三行包含$$$n-1$$$整数,$$$p_1, p_2, \ldots, p_{n-1}$$$; $$$p_i$$$ ($$$p_i \leq i$$$) 描述了城市 $$$p_i$$$ 和 $$$i+1$$$ 之间的道路。
输出
打印一个整数 — 不同计划的数量以 $$$10^9+7$$$ 为模。
示例
输入 #1
4 1 1 1 1 1 2 3
输出 #1
4
输入 #2
4 1 1 1 1 1 2 2
输出 #2
2
输入 #3
4 1 2 1 2 1 1 3
输出 #3
3
注意
对于第一个示例,有 $$$4$$$ 不同的计划:
计划$$$1$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$。
计划$$$2$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$,级别-$$$2$$$:$$$\{1,2\}$$$,$$$\{3,4\}$$$。
计划$$$3$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$,级别-$$$2$$$:$$$\{1\}$$$、$$$\{2\}$$$、$$$\{3\}$$$、$$$\{4\}$$$。
计划 $$$4$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$,级别-$$$2$$$:$$$\{1,2\}$$$,$$$\{3,4\}$$$,级别-$$$3$$$: $$$\{1\}$$$、$$$\{2\}$$$、$$$\{3\}$$$、$$$\{4\}$$$。
对于第二个示例,有 $$$2$$$ 不同的计划:
计划$$$1$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$。
计划$$$2$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$,级别-$$$2$$$:$$$\{1\}$$$、$$$\{2\}$$$、$$$\{3\}$$$、$$$\{4\}$$$。
对于第三个示例,有 $$$3$$$ 不同的计划:
计划$$$1$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$。
计划$$$2$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$,级别-$$$2$$$:$$$\{1,2\}$$$,$$$\{3,4\}$$$。
计划$$$3$$$:级别-$$$1$$$:$$$\{1,2,3,4\}$$$,级别-$$$2$$$:$$$\{1,3\}$$$,$$$\{2\}$$$,$$$\{4\}$$$。