Find the Original Typed String II

Hard

Alice is attempting to type a specific string on her computer.

However, she tends to be clumsy and may press a key for too long, resulting in a character being typed multiple times.

You receive a string word, which represents the final output displayed on Alice's screen.

You are also given a positive integer k.

Find and provide the total count of valid original strings that Alice might have intended to type, if she was trying to type a string of size at least k.

Since the answer may be very large, provide it modulo 10^9+ 7.

Example 1

Input: word = "aabbccdd", k = 7

Output: 5

Explanation: The valid strings are: "aabbccdd", "aabbccd", "aabbcdd", "aabccdd", and "abbccdd".

Example 2

Input: word = "aabbccdd", k = 8

Output: 1

Explanation: The only valid string is "aabbccdd".

Example 3

Input: word = "aaabbb", k = 3

Output: 8

Constraints

1 <= word.length <= 5 * 10^5
word consists only of lowercase English letters.
1 <= k <= 2000

Did this problem appear in one of your interviews?

Responses stay private.

Constraints

Did this problem appear in one of your interviews?

Acceptance rate: 0%