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