{"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\"\u003eGiven you $n,x,k$ , find the value of the following formula:\u003cbr\u003e\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)\\\\$$\u003cbr\u003e\u003cbr\u003e$\\gcd(a_1,a_2,\\ldots ,a_n)$ is the greatest common divisor of $a_1,a_2,...,a_n$.\u003cbr\u003e\u003cbr\u003eThe function $f(x)$ is defined as follows:\u003cbr\u003e\u003cbr\u003eIf there exists an ingeter $k\\ (k\u0026gt;1)$ , and $k^2$ is a divisor of $x$, \u003cbr\u003e then $f(x)\u003d0$, else $f(x)\u003d1$.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains three integers $t,k,x\\ (1\\le t \\le 10^4,1\\le k\\le 10^9,1\\le x\\le 10^9)$\u003cbr\u003e\u003cbr\u003eThen $t$ test cases follow. Each test case contains an integer $n\\ (1\\le n\\le 2\\times 10^5)$"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print one integer — the value of the formula.\u003cbr\u003e\u003cbr\u003eBecause the answer may be very large, please output the answer modulo $10^9+7$."}},{"title":"Sample","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\u003e3 1 3\r\n56\r\n5\r\n20\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e139615686\r\n4017\r\n11554723\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}