Hôm nay, Nam đã học được một bài toán mới, đó chính là số Fibonacci. Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 hoặc 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Công thức truy hồi của dãy Fibonacci là: $$ F(n) = \begin{cases} 1, & \text{khi } n = 1; \\ 1, & \text{khi } n = 2; \\ F(n - 1) + F(n - 2), & \text{khi } n > 2. \end{cases} $$

Cô giáo của Nam đã giao ra một bài toán mới thật hốc búa dành cho Nam như sau: Hãy tìm số Fibonacci thứ ~n~ (~n \leq 10^6~).

Yêu cầu:Tìm số Fibonacci thứ ~n~.

Input

Chỉ có một dòng duy nhất gồm một số nguyên dương ~n~ (~n \leq 10^6~).

Output

Số tự nhiên - số Fibonacci thứ ~n~ modulo ~10^9+7~.

Example input 1

10

Example output 1

55

Note 1

• Các số Fibonacii như sau: ~1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...~