Yêu cầu

Cho dãy số: \(u_n\) thỏa mãn \(u_1 = u_2 = 1\) và \(u_n = 2*u_{n-1} - u_{n-2}\) với mọi số tự nhiên \(n >2\). Nhập vào số nguyên dương n (\(0< n \leq 10^6\)). In ra số hạng thứ n của dãy.

Dữ liệu

Một dòng ghi số \(n\) duy nhất.

Kết quả

Ghi ra số hạng thứ \(n\) của dãy số.

Ví dụ

INPUT

2

OUTPUT

1