"Ai chắp cánh cho đôi chim bay về tổ

Ai dẫn lối cho đôi bạn trẻ của chúng tôi

Tôi nguyện làm cơn gió chiều

Để thổi bùng lên ngọn lửa tình yêu !!!"

Ngân nga thế thôi !! Hiếu tỉnh dậy khỏi cơn mê làm MC.

Cậu ta luôn có niềm đam mê với toán, vì vậy cậu ta chỉ học mỗi toán dẫn tới các môn khác điểm thấp và trượt đại học. Cậu phải làm việc chân tay, lát nền gạch để kiếm sống

Việc chân tay nhưng không cản được đam mê của Hiếu, một ngày cậu ta tự đặt ra 1 bài toán để đố bạn :

Cho 1 hành lang ~2~ x ~N~ được lát bằng các viên gạch ~1~x~2~, ~2~x~2~. Giả sử không có viên nào bị cắt hay trùng lặp và không được đặt 2 viên ~2~x~2~ cạnh nhau

Vậy có bao nhiêu cách lát hành lang này. Lưu ý: Đặt ~1~x~2~ ngang được tính khác trường hợp với 1x2 dọc

Do kết quả có thể lớn nên bạn hãy lấy kết quả khi chia dư cho ~10^{9}+7~

Input Format

• 1 dòng chứa 1 số nguyên dương ~N~( ~10 ≤ N ≤ 10^{6} ~)

Output Format:

• In ra số cách lát hành lang ~2~ x ~N~ thỏa mãn đề bài

Sample Input:

5

Sample output:

19