UOJ Logo Universal Online Judge

UOJ

#452. 【集训队作业2018】彩虹般绚烂

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

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个式子的值,答案对1000000007取模。

输入格式

一行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$43s512MB9
2$10^9$112s512MB9
3$10^9$122s512MB11
4$10^9$$10^9$22s512MB13
5$10^9$$10^9$32s512MB11
6$10^9$$10^9$44s512MB13
7$10^9$$10^9$43s512MB19
8$10^9$$10^9$42s512MB15

下载

样例数据下载