UOJ Logo Universal Online Judge

UOJ

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

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

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

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

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

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

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

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

爱神告诉Y“我可以帮你向y表白,但有一个条件”,爱神随即写下两个函数: f(i)=(ki)ki[i](i是素数时,f(i)=(ki)ki否则f(i)=1)g(i)=(ki)kφ(i)(φ(i)ii)

接着又写下了四个式子: 1.i=1nf(i)2.i=1ng(i)3.i=1nj=1nif(j)nj4.i=1nj=1nig(j)nj 爱神给出了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

限制与约定

测试点编号nkm时间限制空间限制分数
110710943s512MB9
2109112s512MB9
3109122s512MB11
410910922s512MB13
510910932s512MB11
610910944s512MB13
710910943s512MB19
810910942s512MB15

下载

样例数据下载