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