QUESTION 2: SAFE PASSWORDS
You are given two integers n and k.
A password contains exactly n lowercase English letters.
A password is safe if it does not contain k or more consecutive occurrences of the same character.
Count the number of distinct safe passwords. Return the answer modulo 1000000007.
INPUT
One line containing two integers n and k.
CONSTRAINTS
2 <= n <= 100000
2 <= k <= n
OUTPUT
Print the number of safe passwords modulo 1000000007.
EXAMPLE 1
Input:
2 2
Output:
650
Explanation:
There are 26 * 26 = 676 possible passwords.
The 26 passwords with identical characters are unsafe.
The answer is 676 - 26 = 650.
EXAMPLE 2
Input:
3 3
Output:
17550
Explanation:
Only passwords with all three characters equal are unsafe.
The answer is 26 * 26 * 26 - 26 = 17550.
EXAMPLE 3
Input:
3 2
Output:
16250
Explanation:
Every pair of adjacent characters must be different.
The answer is 26 * 25 * 25 = 16250.
For example, aba is safe, but aab is unsafe.