Description

Given three sequences $a=[a_1,a_2,...a_n]$, $b=[b_1,b_2,...b_n]$ and $c=[c_1,c_2,...c_n]$ each containing n non-negative integers. You need to compute the value of $\displaystyle\sum_{p=1}^n\sum_{k=1}^{+\infty }d_{p,k}*c_{p}^k$.

And the sequence $d=[d_{p,1},d_{p,2}...d_{p,n}]$ is calculated by the following rule:

For every integer p $(1 \leqslant p \leqslant n)$, every integer k $(1 \leqslant k \leqslant n)$, $\displaystyle d_{p,k}=\sum_{k=i\oplus j}a_i*b_j$, (the range of i, j is $1\le i\le \frac{n}{p}$, $1\le j\le \frac{n}{p}$). Wherein,the notation ⊕ represents an operation in which the value of each bit of K in the ternary representation is equal to the greatest common divisor of the corresponding bit of I, J in the ternary representation. Formally speaking, decimal numbers $(K)_{10}$, $(I){10}$, $(J){10}$ can be respectively represented as three ternary numbers $(k_{m−1}k_{m−2}...k_0)_3$, $(i_{m−1}i_{m−2}...i_0)_3$, $(j_{m−1}j_{m−2}...j_0)_3$ . For every integer t in $(1 \leqslant t \leqslant m)$, $k_t=gcd(i_t,j_t)$, where $gcd(x,y)$ is the greatest common divisor of x and y, specially, we define that $gcd(x,0)=gcd(0,x)=x$. For example, if $x=(5)_{10}=(012)_3, y=(10)_{10}=(101)_3$, then $k=(111)_3=(13)_{10}$

Output the answer mod $10^9+7$.

Format

Input

There is only one test case for this question.

The first line contains an integer n $(n≤2∗10^5)$ — length of the sequence $a,b,c$.

The second line contains n integers $a_1,a_2,…,a_n (1≤a_i≤10^9)$.

The third line contains n integers $b_1,b_2,…,b_n (1≤b_i≤10^9)$.

The fourth line contains n integers $c_1,c_2,…,c_n (1≤c_i≤10^9)$.

Output

Print an integer, which is the answer modulo $10^9+7$

Samples

4
2 3 4 5
1 2 3 4
9 8 7 6

1643486