Given three sequences $a[1...n]$, $l[1...n]$, and $r[1...n]$, each of length $n$, you need to find the number of sequences $b$ of length $n$ that satisfy all of the following conditions:

1. For $1\leq i\leq n$, $l[i]\leq b[i]\leq r[i]$.
2. For $1\leq i < n$, $b[i] < b[i+1]$.
3. For $1\leq i\leq n$, $a[i]\&b[i]=a[i]$, where $\&$ is the bitwise AND operator.

Since the answer may be very large, output the answer modulo $998244353$.

Input

The first line contains a positive integer $n$.

The second line contains $n$ integers, representing $a[1...n]$.

The third line contains $n$ integers, representing $l[1...n]$.

The fourth line contains $n$ integers, representing $r[1...n]$.

Output

Output the answer modulo $998244353$.

Examples

Input 1

3
0 0 0
0 0 0
10 10 10

Output 1

165

Subtasks

$Task1~(22pts)$: $0\leq a[i],l[i],r[i]\leq 10^5$

$Task2~(26pts)$: For all $1\leq i\leq n$, $a[i]=0$

$Task3~(52pts)$: No additional restrictions

For all data, it is guaranteed that $0\leq a[i],l[i],r[i] < 2^{60}$ and $1\leq n\leq 100$.