You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一棵以 $1$ 为根的 $n$ 个点的树，每个点上有一个物件，节点 $i$ 上的物件的得分为 $a_i$。

除根节点的物件之外，对于每个物件，你可以选择将它移动到父亲节点位置或者不动。

在所有物件移动完毕之后，对于每个节点，若该节点有至少两个物件，则得分为所有物件得分的异或和；否则该节点不得分。每个移动方案的得分为移动后所有节点的得分之和。

求所有 $2^{n−1}$ 种移动方案的得分之和对 $10^9+7$ 取模的结果。

输入格式

从文件 $tempest.in$ 中读入数据。

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

第二行 $n$ 个非负整数 $a_1,a_2,...,a_n$。

第三行 $n$ 个正整数 $f_2,f_3,...,f_n$，其中 $f_i$ 表示第 $i$ 个节点的父亲节点的编号。

输出格式

输出到文件 $tempest.out$ 中。

一行一个非负整数表示答案对 $10^9+7$ 取模的结果。

样例 1 输入

3
1 2 4
1 2

样例 1 输出

12

样例 1 解释

共有 $2^{3−1}=4$ 种不同的方案：

1. 不移动任何物件，最终每个节点上的物件集合分别为 {$1$}, {$2$}, {$4$}，得分为 0。

2. 移动节点 $2$ 上的物件，最终每个节点上的物件集合分别为{$1,2$}, {}, {$4$}，得分为 $1xor2=3$。

3. 移动节点 $3$ 上的物件，最终每个节点上的物件集合分别为{$1$}, {$2,4$}, {}，得分为 $2xor4=6$。

4. 移动节点 $2,3$ 上的物件，最终每个节点上的物件集合分别为{$1,2$}, {$4$}, {}，得分为 $1xor2=3$。

故所有方案的得分之和为 $0+3+6+3=12$。

样例 2 输入

3
1 2 2
1 1

样例 2 输出

7

样例 3 输入

5
0 1 0 2 2
1 1 2 2

样例 3 输出

22

样例 4 输入

4
1 1 1 0
1 2 2

样例 4 输出

2

样例 5

见右侧文件下的 $tempest5.in$ 与 $tempest5.ans$。

数据范围与提示

对于所有测试数据，保证 $1≤n≤10^5，0≤a_i≤10^9$。

每个测试点的具体限制见下表：