题面 样例

题目描述

有一颗 $n$ 个节点的树。初始每个点有点权 $0/1$。你将等概率选择一个点作为起点，然后重复以下过程：

• 若所有点的点权相同，则停止。

• 否则，设你当前所在点为 $s$，等概率选择一个点 $t$（可以等于 $s$），反转点 $t$ 的点权，并且从 $s$ 沿着树上最短距离移动到 $t$。

求整个过程的期望移动距离和。对 $10^9+7$ 取模。

输入格式

从 tree.in 中读入。

第一行一个正整数 $n$。

第二行一个长度为 $n$ 的 01 串来描述每个点的点权。

接下来 $n-1$ 行，第 $i$ 行描述点 $i+1$ 的父亲 $fa_{i+1}(\le i)$。

输出格式

输出到 tree.out 中。

输出答案对 $10^9+7$ 取模的结果。

样例输入 1

2
01
1

样例输出 1

500000004

样例输入 2

3
001
1
1

样例输出 2

638888896

提示

这个数等于 $\frac{95}{36}$。

数据范围

对于所有数据，保证 $n\le 10^5$，且初始局面一定不是终止局面。

对于测试点 $1$，满足 $n=2$。

对于测试点 $2\sim 3$，满足 $n\le 6$。

对于测试点 $4\sim 5$，满足 $n\le 30,fa_{i}=1$。

对于测试点 $6\sim 8$，满足 $n\le 100$。

对于测试点 $9\sim 10$，无特殊约束。