Aslı - being an obsessive person - wants to number every line of her new notebook. But with all the obsessive numbering needs, Aslı wants every number they have written to have a sum of digits of \(\mathbf{K}\).

Aslı can't wrap their head around this and they need your help. Can you tell them how many numbers are there that has at most \(\mathbf{N}\) digits and have a sum of digits of \(\mathbf{K}\)?

Input

Two space-separated numbers \(\mathbf{N}\) and \(\mathbf{K}\) in one line.

Batch #1:

• \(1 \leq \mathbf{N} \leq 5\)
• \(0 \leq \mathbf{K} \leq 45\)

Batch #2:

• \(1 \leq \mathbf{N} \leq 100\)
• \(0 \leq \mathbf{K} \leq 900\)

Output

Count of numbers having \(\mathbf{N}\) or fewer digits and sum of digits of \(\mathbf{K}\). Since this count can be huge, you need to take the modulo \(10^9+7\) before printing it.

Examples

Input:

2 4

Output:

5

Input:

3 3

Output:

10

Explanation

1st Input

• 4, 13, 22, 31, 40

2nd Input

• 3, 12, 21, 30, 102, 111, 120, 201, 210, 300