Mời thành công Loli trong việc về nhà, ông già lại tiếp tục đánh đố Loli bằng một câu hỏi khác. Lần này liên quan tới số Fibonacci. Ông già cần Loli tìm ra số fibonacci thứ ~N~ khi chia dư cho ~1770136969~.

Số Fibonacci là dãy số mà phần tử này là tổng của hai phần tử trước đó. VD: ~0, 1, 1, 2, 3, 5, 8, 13, 21, \dots~

Input:

• Gồm một dòng duy nhất chứa số nguyên ~N~ ~(1 \le N \le 10^6)~.

Output:

• Gồm một dòng duy nhất là kết quả của bài toán.

Sample Input 1

4

Sample Output 1

5

Sample Input 2

6

Sample Output 2

13