Strings With No k Consecutive Identical Characters

Count the lowercase English strings of length n that do not contain k or more consecutive identical letters, modulo 1000000007. At most k−1 identical letters may appear consecutively; do not misread this as allowing k.

输入格式

The input gives n k. Full original bounds: 1≤n≤100000, 1≤k<n, so a valid n is in fact ≥2; do not change this to k≤n or change the forbidden length to k+1.

输出格式

Output one integer answer.

样例 1

输入：

3 2

输出：

16250

样例 2

输入：

2 1

输出：

0

样例 3

输入：

5 4

输出：

11880050

样例说明

The outputs of the three public examples are, in order: 16250; 0; 11880050. They have been checked by independent enumeration or direct simulation.