Appleman有一棵有n个顶点的树。一些顶点(至少一个)为黑色,其他顶点为白色。
考虑由 Appleman 树的 k (0 ≤ k < n) 条边组成的集合。如果 Appleman 从树中删除这些边,那么它将分裂成 (k + 1) 部分。请注意,每个部分都是一棵带有彩色顶点的树。
现在阿普尔曼想知道,以这样的方式分裂树的集合的数量是多少,使得每个结果部分都恰好有一个黑色顶点?求这个数模 1000000007 (109 + 7)。
输入
第一行包含一个整数 n (2 ≤ n ≤ 105) — 树顶点的数量。
第二行包含树的描述:n - 1 个整数 p0, p1, ..., pn - 2 (0 ≤ pi ≤ i)。其中pi表示有一条边连接树的顶点(i+1)和顶点pi。考虑树顶点的编号从 0 到 n-1。
第三行包含顶点颜色的描述:n 个整数 x0, x1, ..., xn - 1(xi 为 0 或 1)。如果 xi 等于 1,则顶点 i 的颜色为黑色。否则,顶点 i 的颜色为白色。
输出
输出单个整数 — 树分割方式的数量以 1000000007 (109 + 7) 为模。
示例
输入 #1
3 0 0 0 1 1
输出 #1
2
输入 #2
6 0 1 1 0 4 1 1 0 0 1 0
输出 #2
1
输入 #3
10 0 1 2 1 4 4 4 0 8 0 0 0 1 0 1 1 0 0 1
输出 #3
27