Weak Hash Function

Time limit: 2s Memory limit: 256MB Input: Output:

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 NN decimal digits from 11 to 99: d1d_1, d2d_2, \dots, dNd_N. The hash is computed by multiplying each digit with the next one and reducing the result using the modulo MM = 107+1910^7 + 19 = 10 000 01910 \ 000 \ 019, until reaching the last digit. Formally:

hashhash = ((\dots ((((d1d2d_1 \cdot d_2) mod MM) d3\cdot d_3) mod MM) \dots) dN\cdot d_N) mod MM

While performing some experiments, a specific output value HH 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 HH when hashed. How many such inputs are there?

Input data

The first line contains two integers, NN and HH.

Output data

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

Constraints and clarifications

  • 1N501 \leq N \leq 50.
  • 1H<10 000 0191 \leq H < 10 \ 000 \ 019.
# Score Constraints
1 0 Examples
2 7 N=1N = 1
3 23 N4N \leq 4
4 8 N7N \leq 7
5 24 N15N \leq 15
6 29 N30N \leq 30
7 9 No additional limitations.

Example 1

stdin

1 4

stdout

1

Explanation

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

Example 2

stdin

2 8

stdout

4

Explanation

In the second sample case, there are four numbers (1818, 2424, 4242, and 8181) with N=2N = 2 digits and whose hash is H=8H = 8.

Log in or sign up to be able to send submissions!