{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e给定三个序列 $a \u003d [a_1,a_2,...a_n]$、$b\u003d [b_1,b_2,...b_n]$ 和 $c\u003d[c_1,c_2,...c_n]$,每个序列包含 $n$ 个非负整数。你需要计算 $\\displaystyle\\sum_{p\u003d1}^n\\sum_{k\u003d1}^{+\\infty }d_{p,k}*c_{p}^k$ 的值。\u003cbr\u003e\u003cbr\u003e序列 $d\u003d[d_{p,1},d_{p,2}...d_{p,n}]$ 的计算规则如下:\u003cbr\u003e\u003cbr\u003e\u0026amp;#8203;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;对于每个整数 $p$ $(1\\le p\\le n)$,每个整数 $k$ $(1\\le k\\le n)$、$\\displaystyle d_{p,k}\u003d\\sum_{k\u003di\\oplus j}a_i*b_j$,**($i$、$j$ 的范围是 $1\\le i\\le \\frac{n}{p}$、$1\\le j\\le \\frac{n}{p}$)**。其中,符号 $\\oplus$ 表示一个操作,其中 $K$ 的三进制表示的每一位的值等于 $I$、$J$ 在三进制表示中对应位的最大公约数。形式上,十进制数 $(K)_{10}$、$(I)_{10},$ $(J)_{10}$ 可以分别表示为三个三进制数 $(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$。对于 $(1\\le t\\le m)$ 中的每个整数 $t$,$k_t\u003dgcd(i_t,j_t)$,其中 $gcd(x, y)$ 是 $x$ 和 $y$ 的最大公约数,特别地,我们定义 $gcd(x,0)\u003dgcd(0,x)\u003dx$。例如,如果 $x\u003d(5)_{10}\u003d(012)_3$、$y\u003d(10)_{10}\u003d(101)_3$,那么 $k\u003d(111)_3\u003d(13)_{10}$\u003cbr\u003e\u003cbr\u003e输出答案对 $10^9+7$ 取模。 \u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"本题只有一个测试用例。\u003cbr\u003e\u003cbr\u003e第一行包含一个整数 $n$ $(n≤2*10^5)$ — 序列 $a,b,c$ 的长度。\u003cbr\u003e\u003cbr\u003e第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$ $(1≤a_i≤10^9)$。\u003cbr\u003e\u003cbr\u003e第三行包含 $n$ 个整数 $b_1,b_2,…,b_n$ $(1≤b_i≤10^9)$。\u003cbr\u003e\u003cbr\u003e第四行包含 $n$ 个整数 $c_1,c_2,…,c_n$ $(1≤c_i≤10^9)$。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"打印一个整数,即答案对 $10^9+7$ 取模。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n2 3 4 5\r\n1 2 3 4\r\n9 8 7 6\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1643486\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}