Alice is typing a string on her keyboard. During typing, she may hold down a key for too long, causing a character to be typed multiple times consecutively.

You are given a string word representing the final text displayed on the screen, and an integer k.

For every consecutive group of identical characters in word, Alice originally intended to type that character between $1$ and the count of that character in the group times.

Return the total number of possible original strings Alice could have intended to type such that the length of the string is at least k. Since the answer may be large, return it modulo $10^9 + 7$.

Constraints:

• $1 \leq$ word.length $\leq 5 imes 10^5$

• word consists only of lowercase English letters.

• $1 \leq$ k $\leq 2000$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.