I love sequences

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\le p\le n)$, every integer $k$ $(1\le k\le 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 $\oplus$ 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\le t\le 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$.

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)$.

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

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

1643486

2021“MINIEYE杯”中国大学生算法设计超级联赛（2）