#P18901. [2026多校联测]和与积

[2026多校联测]和与积

题目描述

给出一个长度为 nn 的数字字符串 SS,其中每个字符都是 00 到 99 之间的数字。

你需要从字符串中选择恰好 kk 个不同的位置。对于一种选择方案,设选中位置上的数字分别为 a1,a2,…,aka_1,a_2,\ldots,a_k,定义:

  • 数字和:sum=a1+a2+⋯+ak\mathrm{sum}=a_1+a_2+\cdots+a_k。
  • 数字积:$\mathrm{product}=a_1\times a_2\times\cdots\times a_k$。

如果同时满足以下条件,则称这种选择方案合法:

  1. sum>0\mathrm{sum}>0。
  2. product\mathrm{product} 能被 sum\mathrm{sum} 整除。

请计算合法的选择方案总数。由于答案可能很大,请输出答案对 109+710^9+7 取模后的结果。

请注意,两种方案被认为不同,当且仅当选择的位置集合不同,且 00 能被任意正整数整除。

输入格式

第一行包含两个正整数 n,kn,k。

第二行包含一个长度为 nn 的数字字符串 SS。

输出格式

输出一个整数,表示合法的选择方案数对 109+710^9+7 取模后的结果。

样例 1

2 2
22
1

样例 2

5 2
12936
1

样例 3

6 2
123450
5

数据范围

对所有数据,保证 1≤k≤n≤1051\le k\le n\le10^5,1≤k≤1001\le k\le100,SS 仅由字符 0 至 9 组成。

  • 对 10%10\% 的数据,保证 n≤20n\le20。
  • 对另 15%15\% 的数据,保证 k≤5k\le5。
  • 对另 20%20\% 的数据,保证 k≤30k\le30。
  • 对所有数据,无额外限制。