Dãy Fibonacci là một trong những dãy số nổi tiếng nhất trong Toán học và Tin học, xuất hiện trong tự nhiên, trong thuật toán và trong nhiều bài toán kinh điển.

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

• ~F_0 = 0~
• ~F_1 = 1~
• ~F_n = F_{n-1} + F_{n-2}~ với mọi ~n ≥ 2~

Nhiệm vụ của bạn là tính số Fibonacci thứ ~n~.

Yêu cầu

Cho một số nguyên không âm ~n~ (với ~n ≥ 2~), hãy tính giá trị ~F_n~ theo công thức:

$$ F_0 = 0,\ F_1 = 1,\ F_n = F_{n-1} + F_{n-2}\quad (n \ge 2) $$

Dữ liệu

• Một dòng duy nhất chứa số nguyên ~n~.

Kết quả

• In ra giá trị ~F_n~ sau khi chia cho ~123456789987654321~ lấy dư

Ví dụ

Ví dụ 1

Input

2

Output

1

Ví dụ 2

Input

7

Output

13

Giải thích

Giải thích ví dụ 1

Với ~n = 2~:

$$ F_2 = F_1 + F_0 = 1 + 0 = 1 $$

Giải thích ví dụ 2

Ta có:

$$ F_0 = 0,\ F_1 = 1,\ F_2 = 1,\ F_3 = 2,\ F_4 = 3,\ F_5 = 5,\ F_6 = 8,\ F_7 = 13 $$

Kết quả là ~13~.

Chấm điểm

Giới hạn

• ~0 ≤ n ≤ 10^{18}~
• Để đạt điểm tối đa cần thuật toán O(log n).

Subtask