Lát gạch số lượng lớn


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Sàn nhà có kích thước $2\times N$. Người ta dùng hai loại gạch $1 \times 2$ và $2\times 1$ để lát gạch.

Hãy đếm số cách lát gạch sao cho lát gạch kín sàn nhà, không đè lên nhau.

Dữ liệu

  • Một dòng duy nhất chứa số nguyên $N \ (1\le N\le 10^{18})$.

Kết quả

  • Kết quả bài toán sau khi chia lấy dư $10^9+7$.

Ví dụ

Ví dụ 1

input

6

output

8

Comments

There are no comments at the moment.