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

0)

 2 12
Returns: 4
 12, 24, 36, and 48 satisfy the conditions.
1)

 3 111
Returns: 9
 All 3-digits numbers divisible by 111 are Increasing Numbers.
2)

 452 10
Returns: 0
 There is no Increasing Number divisible by 10.
3)

 6 58
Returns: 38

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10566

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13906&pm=10566

rng_58

Testers:

PabloGilberto , connect4 , ivan_metelsky

Problem categories:

Dynamic Programming, Math