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 条边相连，除了根结点外，每个结点都有父亲，根结点记为 1 号结点，其它结点分别编号为 2 ∼ 𝑛。𝑛 个点上分别放有一只蚂蚁， 并且每只蚂蚁有一个属性 $𝑎_𝑖$，除了根节点的蚂蚁之外，每只蚂蚁都可以选择向上爬到父亲结点或者不爬（只能爬一次）。在所有蚂蚁都选择完毕之后，我们统计这些蚂蚁产生的快乐值：如果多只蚂蚁在同一点，则产生这些蚂蚁属性的异或 和的快乐值。如果某个点上只有一只蚂蚁或者没有蚂蚁，则不产生快乐值。问所有方案的所有快乐值之和。

由于答案很大，你只需要输出答案对 $10^9 + 7$取模之后的结果就可以了。

输入格式

第一行输入一个正整数 𝑛，表示树的点数。

接下来一行输入 𝑛 个正整数 $𝑎_𝑖$ ，分别表示每一只蚂蚁的属性。

接下来一行输入 𝑛 − 1 个正整数，分别表示 2 ∼ 𝑛 号结点的父亲结点编号。

输出格式

输出一行一个整数表示答案对 $10^9 + 7$ 取模后的结果

3
1 2 4
1 2

12

3
1 2 2
1 1

7

5
0 1 0 2 2
1 1 2 2

22

4
1 1 1 0
1 2 2

2

提示与说明

样例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

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

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

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

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

所有方案的快乐值之和为 0 + 3 + 3 + 1 = 7

数据范围

本题共有 10 个测试点

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

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

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

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

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