该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

【题目描述】

一棵树有 n 个节点，n-1 条边。1 号节点为根节点。

每个节点上有一只猴子，每只猴子有一个属性值：编号为 $i$ 的猴子的属性值为 $a_i$。

除了根节点的猴子之外，每只猴子都可以选择爬到父节点处（只能爬一次），当然也可以选择不爬。当每只猴子都爬（或不爬）后，就产生了一种方案，我们计算该方案所产生的价值：如果一个节点处有两只或更多的猴子，则产生的价值为该节点处所有猴子的属性值的异或和。如果一个节点处没有猴子或者只有一只猴子，则不产生价值。

求：所有方案所有节点产生的所有价值之和。答案可能很大，你只需要输出答案 mod $(10^9 + 7)$ 的值。

【输入格式】

第一行：一个正整数 n，表示节点数。

接下来一行：包含 n 个正整数 $a_i$。

接下来一行：包含 n-1 个正整数，依次表示 2 ∼ n 号节点的父节点编号。

【输出格式】

一个整数，表示答案 mod $(10^9 + 7)$ 的值

【样例 1 输入】

3 
1 2 4 
1 2 

【样例 1 输出】

12 

【样例 1 说明】

树呈一条链，二号节点的父亲是一号节点，三号节点的父亲是二号节点。1，2，3 号节点猴子的属性值分别为 1、2、4。这些猴子共有 4 种爬的方案：

方案 1：[{1,2},{ },{4}] 表示第一个节点有属性值为 1，2 的两只猴子，第二个节点无猴子，第三个节点有属性值为 4 的一只猴子。本方案的价值为 1 ⊕ 2 = 3，其中 ⊕ 表示异或。

方案 2：[{1,2},{4},{ }]，本方案的价值为 3。

方案 3：[{1},{2},{4}]，每个节点上均只有一只猴子，所以价值为 0。

方案 4：[{1},{2,4},{ }]，价值为 2 ⊕ 4 = 6

所有方案的价值之和为 3 + 3 + 0 + 6 = 12。

【样例 2 输入】

3 
1 2 2 
1 1 

【样例 2 输出】

7 

【样例 2 说明】

方案 1：[{1},{2},{2}]

方案 2：[{1,2},{2},{ }]

方案 3：[{1,2},{ },{2}]

方案 4：[{1,2,2},{ },{ }]

所有方案的价值之和为 0 + 3 + 3 + 1 = 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 

【数据范围】

本题共有 10 个测试点

对于 1 测试点，有 1 ≤ n ≤ 20

对于 2 − 3 测试点，有 1 ≤ n ≤ 1000

对于 4 测试点，树是一条链

对于 5 − 6 测试点，树是一个二叉树

对于 7 −10 测试点，树的形态无特殊限制，$1 ≤ n ≤ 10^5 , 0 ≤ a_i ≤ 10^9$