CF1034C Region Separation

秋之王国有 $n$ 个城市，编号从 $1$ 到 $n$。任意两个城市之间可以通过 $n-1$ 条双向道路相互到达。 今年，政$ $府决定将王国划分为若干区域，并设定不同的等级。整个王国为第 $1$ 级区域。每个第 $i$ 级区域，除非已经是最后一级，必须被划分为至少两个第 $i+1$ 级区域。每个城市在每一级只属于一个区域，并且同一级中任意两个属于同一区域的城市，必须能够仅经过同一区域内的城市相互到达。 根据研究，每个城市 $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$ 取模。

对于第一个样例，有 $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\}$。 由 ChatGPT 4.1 翻译