Valid Passwords

A password has length n, contains only lowercase English letters, and must not contain k consecutive identical characters. Count the distinct valid passwords modulo 1,000,000,007.

See below for this site's input/output protocol.

输入格式

One line with n k. 2≤k≤n≤100000.

输出格式

Output the total number of valid passwords modulo 1,000,000,007.

样例 1

输入：

3 2

输出：

16250

样例 2

输入：

3 3

输出：

17550

样例 3

输入：

5 2

输出：

10156250