时空限制

1S/512M

题目描述

给定一个仅包含数字字符的字符串 $S$ 以及一个正整数 $k$。

请你求出，在 $S$ 的所有长度为 $k$ 的子序列中，有多少个子序列组成的数字是 $4$ 的倍数？

由于答案可能很大，将答案对 $10^9 + 7$ 取模。

注意：

1. 允许存在前导 $0$。例如，子序列 "04" 对应的数值为 $4$，它是 $4$ 的倍数；子序列 "00" 对应的数值为 $0$，它也是 $4$ 的倍数。
2. 两个子序列不同，当且仅当它们选择的字符在原字符串中的下标不同。

格式

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示字符串 $S$ 的长度以及待求子序列的长度。 第二行包含一个长度为 $n$ 且仅由数字字符（'0'-'9'）组成的字符串 $S$。

输出格式

输出一个整数，表示满足条件的子序列个数对 $10^9 + 7$ 取模后的结果。

样例

样例输入 #1

4 2
1234

样例输出 #1

2

样例解释 #1

字符串 $S = 1234$，需要求长度为 $2$ 的子序列。所有长度为 $2$ 的子序列及其对应数值如下：

• 下标 $\{1, 2\}$ 组成的子序列为 "12"（数值 $12$），是 $4$ 的倍数。
• 下标 $\{1, 3\}$ 组成的子序列为 "13"（数值 $13$），不是 $4$ 的倍数。
• 下标 $\{1, 4\}$ 组成的子序列为 "14"（数值 $14$），不是 $4$ 的倍数。
• 下标 $\{2, 3\}$ 组成的子序列为 "23"（数值 $23$），不是 $4$ 的倍数。
• 下标 $\{2, 4\}$ 组成的子序列为 "24"（数值 $24$），是 $4$ 的倍数。
• 下标 $\{3, 4\}$ 组成的子序列为 "34"（数值 $34$），不是 $4$ 的倍数。

共有 $2$ 个满足条件的子序列，因此输出 $2$。

样例输入 #2

4 2
0120

样例输出 #2

3

样例解释 #2

长度为 $2$ 且是 $4$ 的倍数的子序列有：

• 下标 $\{1, 4\}$ 组成的子序列 "00"（数值 $0$）
• 下标 $\{2, 3\}$ 组成的子序列 "12"（数值 $12$）
• 下标 $\{3, 4\}$ 组成的子序列 "20"（数值 $20$）

共 $3$ 个。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$20$	$10$
$2$	$20$	$2000$
$3$	$60$	$2\times 10^5$

对于 $100\%$ 的数据，$1 \le k \le n \le 2 \times 10^5$。字符串 $S$ 仅包含字符 '0' 至 '9'。