A97904.皓仔的累乘

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

皓仔不喜欢数字 aa ,具体来说他不喜欢数字表示数位中包含数字 aa 或能被 aa 整除的所有数。

皓仔从 11 累乘到 nn,但他会避开他不喜欢的数字:凡是数位中包含数字 aa 或 能被 aa 整除的所有数,一律跳过不进行累乘。

例如: 假若皓仔不喜欢数字77,那么他就会跳过数位中包含数字 77 或 能被 77 整除的所有数不进行累乘。

求剩余数的累乘乘积, 由于数字可能太大,结果对 109+710^9 + 7 取模。

输入格式

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

输出格式

输出一行一个整数,表示累乘结果,结果对 109+710^9 + 7 取模。

输入输出样例

  • 输入#1

    5 3

    输出#1

    40

说明/提示

【样例解释】

样例一中不喜欢的数字是 33,跳过后的算式为 1×2×4×5=401\times 2\times 4\times 5=40

如果输入为 6 3,由于 66 是能被 33 整除的数,结果同样为 4040

如果输入为 5 2,则算式变为 1×3×5=151\times 3\times 5=15,跳过数位包含 22 和能被 22 整除的数。

【数据范围】

对于所有测试数据保证:2n21052 \leq n \leq 2 \cdot 10^5 , 2a92 \leq a \leq 9

测试点 nn\leq
131\sim3 10001000
4104\sim 10 21052\cdot10^5
首页