Hi everyone,

I’m struggling with this problem, and I don’t have any idea to do it yet. Does anyone know how to solve it?

A positive integer is called a lucky number when the sum of some of its digits equals the sum of its remaining digits. 561743, for example, is a lucky number because 5 + 1 + 4 + 3 = 6 + 7. However, we are about to count the number of unlucky numbers with the length of N and their digits are in the range [0, K], and they could start with a bunch of ‘0’.

Input: N K Output: The number of unlucky numbers

Example 1:

Input

1 5

Output

5

Example 2:

Input

4 3

Output

164