String Splitting

Interview

Time limit1sMemory limit512 MB

Summary

Count the ways to cut a digit string into K nonempty contiguous pieces so that no piece starts with a 0 (the piece "0" alone is allowed).

Level: Medium6 of 10
Topics: Dynamic programming, String, Combinatorics, Prefix sum
Solved: No attempts yet

Problem

You are given a string $S$ consisting of digits. Split $S$ by cutting it $K-1$ times into $K$ nonempty contiguous substrings. Count the number of ways to split $S$ such that no contiguous substring has a leading zero.

Input

The first line gives the length of the string $N$ and the number of contiguous substrings $K$ . ( $1 \le K \le N \le 2{,}500$ )

The second line gives the string $S$ .

Output

Print the number of ways modulo $1{,}000{,}000{,}007$ on the first line.

Hint

A leading zero is any digit 0 that comes before the first nonzero digit in a string of digits.

The string "0" does not have a leading zero.

Examples3

Example 1
Input
```
5 3
00300
```
Expected output
```
1
```
Example 2
Input
```
5 2
00200
```
Expected output
```
0
```
Example 3
Input
```
5 4
12345
```
Expected output
```
4
```