题目描述

给定一棵 $n$ 个点的树，树上每个点初始有一个 $0$ 或 $1$ 的数字。

考虑这样一个过程：

1. 等概率随机选择一个点作为起点
2. 等概率随机选择一个新点并沿着树上的路径移动过去，最后反转这个新点上的数字（注意只反转这个新点上的数字而非经过的所有点的数字）
3. 如果此时整棵树上的所有数字相同，则过程结束；否则回到步骤 $2$

求出期望的移动距离，对 $10^9 + 7$ 取模。

输入格式

第一行一个整数 $n$。

第二行一个长度为 $n$ 的 $01$ 串，表示每个点的初始数字。

接下来 $n - 1$ 行，其中第 $i$ 行一个整数 $f$ 表示一条连接 $i + 1$ 和 $f$ 的边。

输出格式

一行一个整数表示答案。

2
01
1

500000004

3
001
1
1

638888896

数据范围与提示

对于全部数据， $3 \leq n \leq 100000$，保证初始局面不满足终止条件。

• 存在 $10 \%$的数据， $n \leq 5$。
• 存在 $30 \%$的数据， $n \leq 20$。
• 存在 $50 \%$的数据， $n \leq 100$。
• 存在 $70 \%$的数据， $n \leq 1000$。