“有的人浅薄,有的人金玉其表败絮其中。
有一天，你会遇到一个彩虹般绚烂的人，
当你遇到这个人后，会觉得其他人都只是浮云而已。”
——《怦然心动》Y看完这部电影，产生了很大共鸣。
在Y眼中，y就是这个彩虹般绚烂的人。
可是Y并不清楚y的想法，对自己也没有自信。
Y常常这样安慰自己，现在时机未到，要等待，要有耐心。
日有所思，夜游所梦，某一天，Y在梦境中遇到了y，他傻站在y的面前，想说些什么却又说不出口。突然，天空中传来一个声音"这不过是个梦"，他眼前的y便如烟云一般消散了，只见一个背后长有翅膀的长者从远处缓缓靠近。
此人自称是爱神丘比特，Y对此深信不疑，甚至大呼“我从来不迷信，只信爱神”。
爱神告诉Y“我可以帮你向y表白，但有一个条件”，爱神随即写下两个函数: $$ f(i)=(k∗i)^{k∗i∗[i是素数]}\\ (i\text{是素数时},f(i)=(k∗i)^{k∗i}\text{否则}f(i)=1)\\ g(i)=(k∗i)^{k∗\varphi(i)}\\ (\varphi(i)表示小于或等于i的数中与i互质的数的个数) $$
接着又写下了四个式子:
$$ 1.\prod\limits_{i=1}^n f(i)\\ 2.\prod\limits_{i=1}^n g(i)\\ 3.\prod_{i=1}^n\prod_{j=1}^{\lfloor \frac{n}{i}\rfloor}f(j)^{\lfloor\frac{n}{j}\rfloor}\\ 4.\prod_{i=1}^n\prod_{j=1}^{\lfloor \frac{n}{i}\rfloor}g(j)^{\lfloor\frac{n}{j}\rfloor}\\ $$
爱神给出了 $n$ 和 $k$ 的值，并要求 Y 回答前 $m$ 个式子的值，答案对 $1\,000\,000\,007$ 取模。
输入格式
一行 3 个正整数 $n,k,m$，如题所述。
输出格式
输出 $m$ 行，每行一个整数，第 $i$ 行的整数表示编号为 $i$ 的式子的答案。
样例一
input
233 233 4
output
591645143 124162718 818917434 181711594
样例二
input
166666667 1 2
output
734298437 771861883
限制与约定
| 测试点编号 | $n\le$ | $k\le$ | $m\le$ | 时间限制 | 空间限制 | 分数 |
|---|---|---|---|---|---|---|
| 1 | $10^7$ | $10^9$ | 4 | 3s | 512MB | 9 |
| 2 | $10^9$ | 1 | 1 | 2s | 512MB | 9 |
| 3 | $10^9$ | 1 | 2 | 2s | 512MB | 11 |
| 4 | $10^9$ | $10^9$ | 2 | 2s | 512MB | 13 |
| 5 | $10^9$ | $10^9$ | 3 | 2s | 512MB | 11 |
| 6 | $10^9$ | $10^9$ | 4 | 4s | 512MB | 13 |
| 7 | $10^9$ | $10^9$ | 4 | 3s | 512MB | 19 |
| 8 | $10^9$ | $10^9$ | 4 | 2s | 512MB | 15 |