MegaCoolNumbers | Topcoder Archive

Problem Statement

A positive integer is called a cool number of power A if it can be separated into exactly A groups of consecutive digits, where the digits in each group form an arithmetic progression. An arithmetic progression is a sequence of numbers in which the difference between any two consecutive numbers is the same. A positive integer is called a mega cool number of power A if it is a cool number of power A, not a cool number of power A-1, and all its digits are in non-decreasing order.
Determine the number of mega cool numbers of power A that contain exactly N digits (with no leading zeroes). Return this number modulo 1,000,000,007.

Definition

Class:: MegaCoolNumbers
Method:: count
Parameters:: int, int
Returns:: int
Method signature:: int count(int N, int A)
(be sure your method is public)

Constraints

A and N will be between 1 and 1,000, inclusive.

Examples

```
1
```
```
1
```
```
Returns: 9
```
There 9 such numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9.
```
2
```
```
1
```
```
Returns: 45
```
Any two-digit number with non-decreasing digits will be a mega cool number of power 1.
```
2
```
```
2
```
```
Returns: 0
```
There are no such numbers.
```
10
```
```
3
```
```
Returns: 7502
```

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.