#P18875. [IIOT2021]Weak Hash Function
[IIOT2021]Weak Hash Function
题目描述
Luca 正在设计一种简单的哈希函数。输入是一个由 个十进制数字组成的数,每一位都只能是 到 ,不能出现 。
设这些数字从左到右依次为 。哈希函数将所有数字相乘,并对
取模,即
$$\operatorname{hash}(d_1d_2\cdots d_N)=\left(\prod_{i=1}^{N}d_i\right)\bmod M.$$给定 和目标哈希值 ,请计算有多少个不同的 位数,其哈希值恰好为 。
数字的排列顺序不同,视为不同的数。例如,18 和 81 是两个不同的数,即使它们的哈希值相同。
由于答案可能很大,请输出答案对 取模后的结果。
输入格式
输入一行,包含两个整数 。
输出格式
输出一个整数,表示满足条件的数的数量对 取模后的结果。
数据范围
- 。
- 。
样例 1
1 4
1
样例 1 解释
只有一位数 4 满足条件。
样例 2
2 8
4
样例 2 解释
满足条件的数为 18、24、42、81。