Dãy số Fibonacii được định nghĩa như sau:

• \(F_0=0;F_1=1;F_i=F_{i-1}+F_{i-2} (i≥2).\)

Dãy các số Fibonacii đấu tiên: 1, 1, 2, 3, 5, 8, 13, …

Yêu cầu: Cho số nguyên \(N\). Tính \(GCD(f_{2n}, f_{3n})\) % \((10^9+7).\)

Dữ liệu Vào từ file văn bản MFIBO3.INP có cấu trúc:

• Dòng 1 chứa một số nguyên \(N(1≤N≤10^{18}).\)

Kết quả ghi vào file văn bản MFIBO3.OUT có cấu trúc:

• Ghi một số nguyên là kết quả bài toán.

Sample Input

1

Sample Output

1