Định nghĩa số fibo cấp ~x~ bằng công thức sau:

~F_{x, 0}, F_{x, 1}, ..., F_{x, x - 1} = 1~.

~F_{x, i} = \sum_{j = i - (x - (i \; mod \; x))}^{i - 1}F_{x, j}~.

Cho ~2~ số ~n~ và ~x~, bạn cần tìm ~F_{x, n}~ là số fibo cấp ~x~ thứ ~n~ modulo ~10^9+7~.

Input

• Nhập ~2~ số nguyên dương ~n~ và ~x~ ~(n \leq 10^{18}, x \leq 100)~.

Output

• In ra ~F_{x, n}~ modulo ~10^9+7~.

Sample Input 1

10 3

Sample Output 1

56

Sample Input 2

420 69

Sample Output 2

464694677

Note

Khi ~x = 3~, ~11~ số đầu của dãy fibo cấp ~3~ là ~1,1,1,3,4,4,11,15,15,41,56~.

Constraint