Problem Brief

Strings With No k Consecutive Identical Characters

You are given two integers:

n: length of string
k: maximum allowed consecutive identical characters

A string is invalid if it contains k or more consecutive identical characters.

Return the total number of strings of length n formed using lowercase English letters such that no character appears k or more times consecutively.

Return the answer modulo 10^9 + 7.

1Example 1

Input

n = 3, k = 2

Output

16250

Explanation

Total strings of length 3 is 26^3 = 17576.

Invalid strings are those with at least one adjacent equal pair. For this case, the valid count is 16250.

Constraints

Limits and guarantees your solution can rely on.

1 <= n <= 10^5
1 <= k < n

Draft autosaves locally

public int stringsWithNoKConsecutiveIdenticalCharacters(int n, int k) {
  // write your code here
}

Input

Output

16250