{"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\"\u003eAlice is playing a game with Bob.\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.\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 :\u003cbr\u003e1. For each i \u003d 1…N, 1 ≤ b[i] ≤ M\u003cbr\u003e2. gcd(b\u003csub\u003e1\u003c/sub\u003e, b\u003csub\u003e2\u003c/sub\u003e, …, b\u003csub\u003eN\u003c/sub\u003e) \u003d d\u003cbr\u003e3. There will be exactly K position i that ai !\u003d bi (1 ≤ i ≤ n)\u003cbr\u003e\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!\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\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input contains several test cases, terminated by EOF.\u003cbr\u003eThe first line of each test contains three integers N, M, K. (1 ≤ N, M ≤ 300000, 1 ≤ K ≤ 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.\u003cbr\u003e\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test contains 1 lines :\u003cbr\u003eThe line contains M integer, the i-th integer is the answer shows above when d is the i-th number."}},{"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 3 3\r\n3 3 3\r\n3 5 3\r\n1 2 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7 1 0\r\n59 3 0 1 1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eIn the first test case :\u003cbr\u003ewhen d \u003d 1, {b} can be :\u003cbr\u003e(1, 1, 1)\u003cbr\u003e(1, 1, 2)\u003cbr\u003e(1, 2, 1)\u003cbr\u003e(1, 2, 2)\u003cbr\u003e(2, 1, 1)\u003cbr\u003e(2, 1, 2)\u003cbr\u003e(2, 2, 1)\u003cbr\u003ewhen d \u003d 2, {b} can be :\u003cbr\u003e(2, 2, 2)\u003cbr\u003eAnd because {b} must have exactly K number(s) different from {a}, so {b} can\u0027t be (3, 3, 3), so Answer \u003d 0\u003cbr\u003e"}}]}