MegaFactorialDiv2 | Topcoder Archive

Problem Statement

The factorial of the k-th order of a number n is denoted n!k and defined by the following recurrences:
1) n!k = n!(k-1) * (n-1)!k for n > 0 and k > 0
2) n!k = 1 for n = 0
3) n!k = n for k = 0

For example, 7!1 = 7! (the traditional factorial), and 5!3 = 5!2 * 4!3 = (5!1 * 4!2) * 4!3.

You are given ints N and K. Compute the number of distinct divisors of the number N!K. Return the computed number modulo 1,000,000,009.

Definition

Class:: MegaFactorialDiv2
Method:: countDivisors
Parameters:: int, int
Returns:: int
Method signature:: int countDivisors(int N, int K)
(be sure your method is public)

Constraints

N will be between 1 and 1000, inclusive.
K will be between 1 and 100, inclusive.

Examples

```
3
```
```
1
```
```
Returns: 4
```
3!1 = 3! = 6. The divisors of 6 are 1, 2, 3 and 6.
```
3
```
```
2
```
```
Returns: 6
```
3!2 = 3!1 * 2!2 = 3! * 2!1 * 1!2 = 3! * 2! * 1!1 * 0!2 = 3! * 2! * 1! * 1 = 12. The divisors of 12 are 1, 2, 3, 4, 6 and 12.
```
4
```
```
2
```
```
Returns: 18
```
4!2 is equal to 288.
```
6
```
```
3
```
```
Returns: 1392
```
```
100
```
```
2
```
```
Returns: 321266186
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.