Lát gạch số lượng lớn
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