We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- All Contests
- ProjectEuler+
- Project Euler #231: The prime factorisation of binomial coefficients

# Project Euler #231: The prime factorisation of binomial coefficients

# 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**

```
14
```

**Explanation 1**

.

- : the answer is .

**Sample Input 2**

```
22 6 4
```

**Sample Output 2**

```
57
1210
11730
50629
```

**Explanation 2**

.

- : .
- : .
- : .
- : .