Dãy tỷ lệ

REF: OLP Chuyên tin

Xét dãy số Fibonacci được định nghĩa ~F_1 = F_2 = 1; F_n = F_{n-1} + F_{n-2}~ với ~n > 2~.

Dãy số nguyên ~a = \{a_1, a_2, \ldots, a_n\}~ được gọi là dãy tỉ lệ của ~F_n~ nếu ta có:

~\frac{a_1}{F_1} = \frac{a_2}{F_2} = \ldots = \frac{a_n}{F_n}~.

Cho ~a_1~ và ~n~, hãy tính tổng ~S = a_1 + a_2 + \ldots + a_n~ và đưa ra số dư của ~S~ khi chia cho ~10^9 + 7~.

Input

Dòng duy nhất ghi hai số nguyên ~a_1~ và ~n~ thỏa ~0 < a_1, n \le 10^{15}~.

Output

In ra kết quả cần tính.

Samples

3 5

36