提示: 欢迎访问OurACM平台。
Problem 1754 Count Problem

Accept: 60    Submit: 261
Time Limit: 10000 mSec    Memory Limit : 65536 KB

Problem Description

给出一个集合{a1^a1,a2^a2....,an^an}(n<=70000),AekdyCoin希望你告诉他有集中方案选取数(不能不选),使它们的和可以被C整除,其中ai表示第i个素数.

Input

输入包括多组数据,数据的第1行包括3个数n,c,l.表示下面集合的元素个数(既集合为前n个素数),c的值和你需要输出的答案的最右位数(1<=n<=70000,c<=100,1<=l<=16)

Output

输出一行答案

Sample Input

10 53 2 70000 13 10

Sample Output

12 8152962121

Source

FZU 2009 Summer Training IV--Number Theory

Submit  Back  Status  Discuss