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

Y看完这部电影，产生了很大共鸣。

在Y眼中，y就是这个彩虹般绚烂的人。

可是Y并不清楚y的想法，对自己也没有自信。

Y常常这样安慰自己，现在时机未到，要等待，要有耐心。

日有所思，夜游所梦，某一天，Y在梦境中遇到了y，他傻站在y的面前，想说些什么却又说不出口。突然，天空中传来一个声音"这不过是个梦"，他眼前的y便如烟云一般消散了，只见一个背后长有翅膀的长者从远处缓缓靠近。

此人自称是爱神丘比特，Y对此深信不疑，甚至大呼“我从来不迷信，只信爱神”。

爱神告诉Y“我可以帮你向y表白，但有一个条件”，爱神随即写下两个函数: $$\begin{gathered} f(i)=(k\ast i{)}^{k\ast i\ast [i\mathrm{是}\mathrm{素}\mathrm{数}]} \\ (i\text{是素数时},f(i)=(k\ast i{)}^{k\ast i}\text{否则}f(i)=1) \\ g(i)=(k\ast i{)}^{k\ast \phi (i)} \\ (\phi (i)\mathrm{表}\mathrm{示}\mathrm{小}\mathrm{于}\mathrm{或}\mathrm{等}\mathrm{于}i\mathrm{的}\mathrm{数}\mathrm{中}\mathrm{与}i\mathrm{互}\mathrm{质}\mathrm{的}\mathrm{数}\mathrm{的}\mathrm{个}\mathrm{数}) \end{gathered}$$

接着又写下了四个式子: $$\begin{gathered} 1.\prod _{i=1}^{n}f(i) \\ 2.\prod _{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 } \end{gathered}$$ 爱神给出了n和k的值，并要求Y回答前m个式子的值，答案对1000000007取模。

输入格式

一行3个正整数n,k,m，如题所述。

输出格式

输出m行，每行一个整数，第i行的整数表示编号为i的式子的答案。

样例一

input

233 233 4

output

591645143
124162718
818917434
181711594

样例二

input

166666667 1 2

output

734298437
771861883

限制与约定

下载

样例数据下载