“有的人浅薄,有的人金玉其表败絮其中。
 有一天，你会遇到一个彩虹般绚烂的人，
 当你遇到这个人后，会觉得其他人都只是浮云而已。”                                    
                                                     ——《怦然心动》

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

限制与约定