Project Euler #231: The prime factorisation of binomial coefficients

_{This problem is a programming version of Problem 231 from projecteuler.net}

For a positive integer where are distinct primes, the prime omega function is defined as .

For example, , and .

Let

That is,

is the sum of all positive divisors

of the binomial coefficient

satisfying

.

Given

and

, find

modulo

, for all

Input Format

The only line of each test file contains three space-separated integers: , and .

Constraints

Output Format

Print exactly lines, the -th line must contain the answer when .

Sample Input 0

15 9 3

Sample Output 0

36
466
2556

Explanation 0

Sample Input 1

16 3 1

Sample Output 1

Explanation 1

Sample Input 2

22 6 4

Sample Output 2

Explanation 2