A-Hansu

Time limit

Memory limit

128 MB

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.