{"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 Alice is playing a game with Bob.\n \u003cbr\u003eAlice shows N integers a\u003csub\u003e1\u003c/sub\u003e, a\u003csub\u003e2\u003c/sub\u003e, …, a\u003csub\u003eN\u003c/sub\u003e, and M, K. She says each integers 1 ≤ a\u003csub\u003ei\u003c/sub\u003e ≤ M.\n \u003cbr\u003eAnd now Alice wants to ask for each d \u003d 1 to M, how many different sequences b\u003csub\u003e1\u003c/sub\u003e, b\u003csub\u003e2\u003c/sub\u003e, …, b\u003csub\u003eN\u003c/sub\u003e. which satisfies :\n \u003cbr\u003e1. For each i \u003d 1…N, 1 ≤ b[i] ≤ M\n \u003cbr\u003e2. gcd(b\u003csub\u003e1\u003c/sub\u003e, b\u003csub\u003e2\u003c/sub\u003e, …, b\u003csub\u003eN\u003c/sub\u003e) \u003d d\n \u003cbr\u003e3. There will be exactly K position i that ai !\u003d bi (1 ≤ i ≤ n)\n \u003cbr\u003e\n \u003cbr\u003eAlice thinks that the answer will be too large. In order not to annoy Bob, she only wants to know the answer modulo 1000000007.Bob can not solve the problem. Now he asks you for HELP!\n \u003cbr\u003e\u003cstrong\u003eNotes\u003c/strong\u003e: gcd(x\u003csub\u003e1\u003c/sub\u003e, x\u003csub\u003e2\u003c/sub\u003e, …, x\u003csub\u003en\u003c/sub\u003e) is the greatest common divisor of x\u003csub\u003e1\u003c/sub\u003e, x\u003csub\u003e2\u003c/sub\u003e, …, x\u003csub\u003en\u003c/sub\u003e\n\u003c/div\u003e\n给定一个长度为n的序列a,且 1\u003c\u003da[i]\u003c\u003dm,求分别有多少个序列b,使得GCD(b[1],b[2],...b[n])\u003dx (1\u003c\u003dx\u003c\u003dm),且正好有k个b[i]!\u003da[i]。"}},{"title":"Input","value":{"format":"HTML","content":"The input contains several test cases, terminated by EOF.\n\u003cbr\u003eThe first line of each test contains three integers N, M, K. (1 ≤ N, M ≤ 300000, 1 ≤ K ≤ N)\n\u003cbr\u003eThe second line contains N integers: a\u003csub\u003e1\u003c/sub\u003e, a\u003csub\u003e2\u003c/sub\u003e, ..., a\u003csub\u003en\u003c/sub\u003e (1 ≤ a\u003csub\u003ei\u003c/sub\u003e ≤ M) which is original sequence.\n\u003cbr\u003e\n\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test contains 1 lines :\n\u003cbr\u003eThe line contains M integer, the i-th integer is the answer shows above when d is the i-th number."}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e3 3 3\n3 3 3\n3 5 3\n1 2 3\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e7 1 0\n59 3 0 1 1\u003c/pre\u003e"}}]}