ml3 | Weak Hash Function

To help a friend who is working on the internals of the Java Virtual Machine, Luca is working on a new hash function. Hash functions are meant to take as an input a large value, process it according to internal rules, and finally produce a smaller value.

Since the number of possible different output values is limited and smaller than the number of possible input values, by using a hash function one accepts the risk of collisions. A collision happens when two distinct input values, when hashed, give the same output value.

Luca’s algorithm is rather simple, as the use case admits the possibility of collisions, provided that they don’t grow too much. The input number is a sequence of $N$ decimal digits from $1$ to $9$: $d_1$, $d_2$, $\dots$, $d_N$. The hash is computed by multiplying each digit with the next one and reducing the result using the modulo $M$ = $10^7 + 19$ = $10 \ 000 \ 019$, until reaching the last digit. Formally:

$hash$ = (($\dots$ (((($d_1 \cdot d_2$) mod $M$) $\cdot d_3$) mod $M$) $\dots$) $\cdot d_N$) mod $M$

While performing some experiments, a specific output value $H$ seems to be occurring way more often than all other values. Luca is now worried that for some reason there might be a lot of different inputs that produce exactly $H$ when hashed. How many such inputs are there?

Input data

The first line contains two integers, $N$ and $H$.

Output data

You need to write a single line with an integer: the number of different values that produce $H$ when hashed with Luca’s algorithm. Since this number may be large, report it modulo $10 \ 000 \ 019$.

Constraints and clarifications

• $1 \leq N \leq 50$.
• $1 \leq H < 10 \ 000 \ 019$.

Example 1

stdin

1 4

stdout

1

Explanation

In the first sample case there is just one number ($4$) with $N = 1$ digits and whose hash is $H = 4$.

Example 2

stdin

2 8

stdout

4

Explanation

In the second sample case, there are four numbers ($18$, $24$, $42$, and $81$) with $N = 2$ digits and whose hash is $H = 8$.