Description

给定长度为 $n$ 的 排列 $b$ 和 序列 $c$ ，询问有多少个长度为 $n$ 的序列 $A$ ，满足以下两个条件：

1. $0 \leqslant A_i<2^{60}$

2. $A_i$ $xor$ $A_{b_i} \leqslant c_i$

答案对998244353 取模。

Format

Input

第一行一个正整数$n$，含义同题面描述。

第二行共$n$ 个正整数，第$i$ 个表示$b_i$，$b$ 是个排列。

第三行共$n$ 个正整数，第$i$ 个表示$c_i$，含义同题面描述。

Output

一行一个整数，表示答案。

Samples

3
2 3 1
2 1 2

416046766

Limitation

对于$10\%$的数据:$n \leqslant 5,c_i<2^3$

对于$30\%$的数据:$n \leqslant 1000,c_i<2^7$

对于$50\%$的数据:$n \leqslant 1000,c_i<2^{14}$

对于另$20\%$的数据:总存在$0 \leqslant j \leqslant 60$，满足$c_i=(2^j)-1$

对于另$10\%$的数据:满足$n$为偶数，当$i$为奇数时，$b_i=i+1$；当$i$为偶数时,$b_i=i-1$

对于$100\%$的数据：$3 \leqslant n \leqslant 100000,0 \leqslant c_i<2^{60}$