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