Đị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-(imodx))}^{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\le {10}^{18},x\le 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