IncreasingNumber | Topcoder Archive

Problem Statement

A positive integer is called Increasing Number if its digits are in non-descending order from left to right in decimal notation. For example, 1234, 111, 58 and 8899 are Increasing Numbers, while 314, 7654 and 2009 are not.

You are given a long digits and an int divisor. Calculate the number of Increasing Numbers that satisfy both of the following conditions and return this number modulo 1,000,000,007.

The number contains exactly digits digits in the decimal notation with no leading zeroes.
The number is divisible by divisor.

Definition

Class:: IncreasingNumber
Method:: countNumbers
Parameters:: long, int
Returns:: int
Method signature:: int countNumbers(long digits, int divisor)
(be sure your method is public)

Constraints

digits will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive.
divisor will be between 1 and 500, inclusive.

Examples

```
2
```
```
12
```
```
Returns: 4
```
12, 24, 36, and 48 satisfy the conditions.
```
3
```
```
111
```
```
Returns: 9
```
All 3-digits numbers divisible by 111 are Increasing Numbers.
```
452
```
```
10
```
```
Returns: 0
```
There is no Increasing Number divisible by 10.
```
6
```
```
58
```
```
Returns: 38
```

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.