← 返回题目列表

Codeforces · 520/E

E. 优点无处不在

中文机器翻译题面 查看原题

Vasya 正在上一堂极其无聊的数学课。为了好玩,他拿了一张纸,在一行写下了n个数字。之后,瓦夏开始写出不同的方法,在行中的某些数字之间添加加号(“+”),从而得到正确的算术表达式;形式上,这样的分区中没有两个加号可以站在一起(任何两个相邻的加号之间必须至少有一个数字),并且没有加号可以站在一行的开头或结尾。例如,在字符串 100500 中,方式 100500(不添加加号)、1+00+500 或 10050+0 是正确的,方式 100++500、+1+0+0+5+0+0 或 100500+ 是不正确的。

课程很长,Vasya 已经写出了将 k 个加号精确放置在一串数字中的所有正确方法。此时,他被老师发现很有趣,并给了他在课程结束时计算所有算术表达式结果的总和的任务(在计算表达式的值时,应忽略前导零)。由于答案可能很大,Vasya 只能得到模 109 + 7 的余数。帮助他!

输入

第一行包含两个整数 n 和 k (0 ≤ k < n ≤ 105)。

第二行包含一个由 n 位数字组成的字符串。

输出

打印对 109 + 7 取模的问题的答案。

示例

输入 #1

3 1
108

输出 #1

27

输入 #2

3 2
108

输出 #2

9

注意

在第一个示例中,结果等于 (1 + 08) + (10 + 8) = 27。

在第二个示例中,结果等于 1 + 0 + 8 = 9。