Description:


现在要给一个长度为 \(n\) 数字串上面加上恰好 \(k\) 个加号,把所有可能的算术结果相加起来。
加号加到数字串中间之后要形成正确的算术表达式。规则是:没有两个加号连在一起,两个加号之间至少要有一位数字,加号不能加在开头,也不能加在结尾。比如数字串是 \(10500\) ,那么 \(100500\) (加0个加号), \(1+00+500\) 或者 \(10050+0\) 这些放置的加号都是合法的,而 \(100++500\) , \(+1+0+0+5+0+0\)\(100500+\) 都是非法的。
结果比较大,对 \(10^9+7\) 取余输出即可。
样例解释:
在第一个例子中 \((1+08)+(10+8)=27\)
在第二个例子中 \(1+0+8=9\)

Input:


单组测试数据。
第一行有两个整数 \(n\)\(k\) ( \(0\le k < n\le 10^5\) )。
第二行包含 \(n\) 位数字。

Output:


输出结果占一行。

Sample Input:


Sample Output:


题解:


我们考虑第 \(i\) 为数字 \(a_i\) ,分别出现在个位、十位、百位……的情况,可以发现答案就是(注意当长度达到 \(j=n-i\) 时,应当单独计算):

\[ \sum_{j = 0}^{n-i-1} 10^j\cdot a_i \binom{n-j-2}{k-1} + 10^{n-i}\cdot a_i \binom{i-1}{k}\]

然后累加:

预处理前缀和,就可以做到 \(O(n)\)