## Lucky Tickets AdvancedProblem #110 |

This is an advanced version of the Lucky Tickets problem.

Values here are going to be slightly greater so that it is not possible to use direct count of sums as you probably did and some "dynamic programming" approach should be invented.

Please note that result could be long enough and some languages have no built-in abilities to store such values. E.g. with

`C++`

neither `long long`

nor `double`

will do. You may prefer to switch to
`Python`

or `Java`

temporarily, or implement "long arithmetics" representing values as arrays in such case.
**input data** contains two values: `N`

- the length of the ticket number and `B`

- the base of numeral system.

**answer** should contain the amount of lucky tickets.

*Note: to simplify the matter, N is always even and B do not exceed 9.*

Example:

```
input data:
22 8
answer:
2719720106419046288
```

You need to login to get test data and submit solution.