← 返回比赛

已结束 GESP欢乐赛#64

← 上一题下一题 →

A7109 | $皓仔的累乘$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

皓仔不喜欢数字 $a$ ，具体来说他不喜欢数字表示数位中包含数字 $a$ 或能被 $a$ 整除的所有数。 皓仔从 $1$ 累乘到 $n$，但他会避开他不喜欢的数字：凡是数位中包含数字 $a$ 或 能被 $a$ 整除的所有数，一律跳过不进行累乘。 例如: 假若皓仔不喜欢数字$7$，那么他就会跳过数位中包含数字 $7$ 或 能被 $7$ 整除的所有数不进行累乘。 求剩余数的累乘乘积， 由于数字可能太大，结果对 $10^9 + 7$ 取模。

输入格式

输入一行两个整数 $n,a$， 代表累乘的范围，以及皓仔不喜欢的数字。

输出格式

输出一行一个整数，表示累乘结果，结果对 $10^9 + 7$ 取模。

输入输出样例

输入 #1

5 3

输出 #1

【样例解释】 样例一中不喜欢的数字是 $3$，跳过后的算式为 $1\times 2\times 4\times 5=40$。 如果输入为 6 3，由于 $6$ 是能被 $3$ 整除的数，结果同样为 $40$。 如果输入为 5 2，则算式变为 $1\times 3\times 5=15$，跳过数位包含 $2$ 和能被 $2$ 整除的数。 【数据范围】 对于所有测试数据保证：$2 \leq n \leq 2 \cdot 10^5$ , $2 \leq a \leq 9$ 。 测试点$n\leq$$1\sim3$$1000$$4\sim 10$$2\cdot10^5$

C++ 编辑器

输入

输出