爬

题目描述

鸡尾酒很喜欢让别人爬，于是他种了一棵树。然后在树上放了 $n$ 只蚂蚁，看它们爬。

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

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

输入格式

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

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

接下来一行输入 $n-1$ 个正整数，分别表示 $2\sim n$ 号结点的父亲结点编号。

输出格式

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

样例 1

3
1 2 4
1 2

12

树呈一条链，二号结点的父亲是一号结点，三号结点的父亲是二号结点。$1,2,3$ 号结点蚂蚁的属性值分别为 $1,2,4$。这些蚂蚁共有 $4$ 种爬的方案：

方案 $1$：$[\{1,2\},\{\},\{4\}]$ 表示第一个结点有属性值为 $1,2$ 的两只蚂蚁，第二个结点无蚂蚁，第三个结点有属性值为 $4$ 的一只蚂蚁。本方案的快乐值为 $1\oplus2=3$，其中 $\oplus$ 表示异或。

方案 $2$：$[\{1,2\},\{4\},\{\}]$，本方案的快乐值为 $3$。

方案 $3$：$[\{1\},\{2\},\{4\}]$，没有结点上有大于等于两只蚂蚁，所以快乐值为 $0$。

方案 $4$：$[\{1\},\{2,4\},\{\}]$，快乐值为 $2\oplus4=6$。

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

样例 2

3
1 2 2
1 1

7

方案 $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

22

样例 4

4
1 1 1 0
1 2 2

2

数据范围

本题共有 $10$ 个测试点。

对于 $1$ 测试点，有 $1\le n\le20$。

对于 $2$-$3$ 测试点，有 $1\le n\le1000$。

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

对于 $5$-$6$ 测试点，树是一个二叉树。

对于 $7$-$10$ 测试点，树的形态无特殊限制，$1\le n\le10^5$，$0\le a_i\le10^9$。