{"trustable":false,"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\n 给你 $n,x,k$ , 计算下列式子的值:\n \u003cbr\u003e\n \u003cbr\u003e$ \\sum_{a_1\u003d1}^{n}\\sum_{a_2\u003d1}^{n}\\ldots \\sum_{a_x\u003d1}^{n}\\left (\\prod_{j\u003d1}^{x}a_j^k\\right )f(\\gcd(a_1,a_2,\\ldots ,a_x))\\cdot \\gcd(a_1,a_2,\\ldots ,a_x)$\n \u003cbr\u003e\n \u003cbr\u003e$\\gcd(a_1,a_2,\\ldots ,a_n)$ 是 $a_1,a_2,...,a_n$ 的最大公因数.\n \u003cbr\u003e\n \u003cbr\u003e $f(x)$ 的定义如下:\n \u003cbr\u003e\n \u003cbr\u003e如果存在整数 $k\\ (k\u0026gt;1)$ , 且 $k^2$ 整除 $x$, \n \u003cbr\u003e 那么 $f(x)\u003d0$, 否则 $f(x)\u003d1$.\n \u003cbr\u003e\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"第一行包含三个整数 $t,k,x\\ (1\\le t \\le 10^4,1\\le k\\le 10^9,1\\le x\\le 10^9)$\n\u003cbr\u003e\n\u003cbr\u003e接下来有 $t$ 组测试. 每组测试包含一个 $n\\ (1\\le n\\le 2\\times 10^5)$"}},{"title":"Output","value":{"format":"HTML","content":"对于每组测试,输出一个整数 ― 上述表达式的值.\n\u003cbr\u003e\n\u003cbr\u003e因为答案可能很大,所以你需要对 $10^9+7$ 取模."}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e3 1 3\n56\n5\n20\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e139615686\n4017\n11554723\n\u003c/pre\u003e"}}]}