Trong bài giảng về kỹ thuật đệ quy, anh Lazyman đã kể một câu chuyện rất hay về nhà Toán học nổi tiếng: François Édouard Anatole Lucas (1842-1891). Có một dãy số được đặt theo tên ông nhằm vinh danh các nghiên cứu của ông về các dãy số nguyên có những ứng dụng quan trọng trong thực tế: dãy số Lucas.

Cách tính số Lucas khá giống số Fibonacci: bắt đầu bằng ~2~ và ~1~, mỗi số tiếp theo bằng tổng của hai số liền trước. Thậm chí công thức tổng quát của nó còn đẹp hơn so với của Fiboacci:

~{{L}_{n}}={{\left( \frac{1-\sqrt{5}}{2} \right)}^{n}}+{{\left( \frac{1+\sqrt{5}}{2} \right)}^{n}}~

Các số đầu tiên của dãy Lucas: ~2,1,3,4,7,11,18,29,47,76,123,...~

Anh Lazyman đã yêu cầu các SV của CLB H3.2 hãy cài đặt đệ quy để tính số hạng thứ ~n~ của dãy này. Các bạn đều rất hào hứng và code ra rất nhanh. Thế là anh bèn nâng độ khó lên "chút xíu" bằng cách cho số ~n~ lên lớn hơn. Điều này có thể kéo theo giá trị của dãy Lucas thu được rất lớn nên kết quả sẽ phải chia dư cho ~10^9+7.~ Bạn hãy giúp các SV của CLB H3.2 khử đệ quy cho bài này nhé!

Input:

Một số nguyên dương ~n~ duy nhất có giá trị không quá ~10^{1000}~.

Output:

Câu trả lời của bài toán.

Sample input 1.

1

Sample output 1.

2

Sample input 2.

2

Sample output 2.

1

Sample input 3.

2554496573107241984

Sample output 3.

97012495

Ghi chú: hãy đọc kỹ giới hạn của đề bài, là ~10~ mũ ~1000~, bạn không nhìn nhầm đâu.