Bạn có vô số viên gạch domino kích thước ~2*1~. Hỏi có bao nhiêu cách để lát kín một sàn nhà hình chữ nhật kích thước ~2*n~ bằng các viên gạch domino ~2*1~.

Yêu cầu: Tính và in ra số cách để lát kín một sàn nhà kích thước ~2*n~ bằng các viên gạch ~2*1~.

Input

Một số nguyên dương ~n~ - chiều dài của sàn (~1 \leq n \leq 10^6~).

Output

Một số nguyên - số cách lát kín modulo ~10^9~.

Example input 1

10

Example output 1

89