#P18901. [2026多校联测]和与积
[2026多校联测]和与积
题目描述
给出一个长度为 的数字字符串 ,其中每个字符都是 到 之间的数字。
你需要从字符串中选择恰好 个不同的位置。对于一种选择方案,设选中位置上的数字分别为 ,定义:
- 数字和:。
- 数字积:$\mathrm{product}=a_1\times a_2\times\cdots\times a_k$。
如果同时满足以下条件,则称这种选择方案合法:
- 。
- 能被 整除。
请计算合法的选择方案总数。由于答案可能很大,请输出答案对 取模后的结果。
请注意,两种方案被认为不同,当且仅当选择的位置集合不同,且 能被任意正整数整除。
输入格式
第一行包含两个正整数 。
第二行包含一个长度为 的数字字符串 。
输出格式
输出一个整数,表示合法的选择方案数对 取模后的结果。
样例 1
2 2
22
1
样例 2
5 2
12936
1
样例 3
6 2
123450
5
数据范围
对所有数据,保证 ,, 仅由字符 0 至 9 组成。
- 对 的数据,保证 。
- 对另 的数据,保证 。
- 对另 的数据,保证 。
- 对所有数据,无额外限制。