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

Description

给定一棵以1号节点为根的树，每个节点有一个小朋友，i号点处小朋友的心情用ai表示。现在除了根节点的小朋友以外，其他小朋友都可以选择留在原地，或者走向父亲节点。

在所有小朋友选择完毕之后，某个节点的快乐程度定义为该节点上所有小朋友心情的异或和。特别注意，如果某个节点上只有一个小朋友或者没有小朋友，那么该节点的快乐程度为0。一种选择方案的快乐值等于所有节点的快乐程度之和。

请你求出所有方案的总快乐程度对1e9+7取模的结果。

Format

Input

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

接下来n个正整数ai，表示每个小朋友的心情值。

接下来一行n-1个正整数，分别表示2~n号节点的父亲节点编号。

Output

输出一个整数表示答案对1e9+7取模的结果。

Samples

3
1 2 4
1 2

12

5
0 1 0 2 2
1 1 2 2

22

Limitation

对于 10% 的数据，$1 \leq n \leq 20$

对于另外 20% 的数据， $1 \leq n \leq 1000$

对于另外 10% 的数据，树是一条链。

对于另外 20% 的数据， 树是二叉树。

对于 100% 的数据，$1 \leq n \leq 10^5,0 \leq a_i \leq 10^9$