#P18875. [IIOT2021]Weak Hash Function

[IIOT2021]Weak Hash Function

题目描述

Luca 正在设计一种简单的哈希函数。输入是一个由 NN 个十进制数字组成的数,每一位都只能是 11 到 99,不能出现 00。

设这些数字从左到右依次为 d1,d2,…,dNd_1,d_2,\ldots,d_N。哈希函数将所有数字相乘,并对

M=107+19=10 000 019M=10^7+19=10\,000\,019

取模,即

$$\operatorname{hash}(d_1d_2\cdots d_N)=\left(\prod_{i=1}^{N}d_i\right)\bmod M.$$

给定 NN 和目标哈希值 HH,请计算有多少个不同的 NN 位数,其哈希值恰好为 HH。

数字的排列顺序不同,视为不同的数。例如,18 和 81 是两个不同的数,即使它们的哈希值相同。

由于答案可能很大,请输出答案对 10 000 01910\,000\,019 取模后的结果。

输入格式

输入一行,包含两个整数 N,HN,H。

输出格式

输出一个整数,表示满足条件的数的数量对 10 000 01910\,000\,019 取模后的结果。

数据范围

  • 1≤N≤501\le N\le50。
  • 1≤H<10 000 0191\le H<10\,000\,019。

样例 1

1 4
1

样例 1 解释

只有一位数 4 满足条件。

样例 2

2 8
4

样例 2 解释

满足条件的数为 18、24、42、81。