A-Hansu

Time limit2sMemory limit128 MB

Summary

Count N-digit numbers with nondecreasing digits whose minimum partition into consecutive arithmetic-progression blocks is exactly A, modulo 1e9+7.

Level: Hard8 of 10
Topics: Combinatorics, Dynamic programming, Math, Greedy
Solved: No attempts yet

Problem

A number X is called an A-Hansu if its digits can be divided into A nonempty consecutive groups and, inside each group, the digits form an arithmetic progression.

A positive integer X is called a true A-Hansu if it is an A-Hansu but not an (A-1)-Hansu, and the digits of X are in nondecreasing order from left to right.

Given N and A, count the true A-Hansu numbers that have exactly N digits and whose first digit is not 0.

Input

The first line contains two natural numbers N and A. Both numbers are at most 1,000.

Output

Print the number of N-digit true A-Hansu numbers modulo 1,000,000,007.

Examples4

Example 1
Input
```
1 1
```
Expected output
```
9
```
Example 2
Input
```
2 1
```
Expected output
```
45
```
Example 3
Input
```
2 2
```
Expected output
```
0
```
Example 4
Input
```
10 3
```
Expected output
```
7502
```