Sau chuỗi trận đầu mùa Premier League 2025-2026 bết bát khiến người hâm mộ phải "chui vào hang", thầy Quyết - một fan cứng của Manchester United - đã mất ngủ 7 ngày 7 đêm để tìm nguyên nhân.

Bằng kiến thức Thần số học uyên thâm, thầy nhận ra vấn đề không nằm ở huấn luyện viên, mà nằm ở "phong thủy" tuyến giữa. Thầy khẳng định: "MU đá kém là do thiếu sự kết hợp hoàn hảo giữa một số 6 (tiền vệ phòng ngự mỏ neo) và một số 8 (tiền vệ con thoi box-to-box)".

Theo lý thuyết của thầy, một đội hình "bất bại" phải được vận hành dựa trên các "Mã Gen Chiến Thắng". Một Mã Gen Chiến Thắng hợp lệ là một chuỗi ký tự chỉ bao gồm hai chữ số 6 và 8.

• Số 6 đại diện cho những pha tắc bóng dũng mãnh.
• Số 8 đại diện cho những đường chuyền kiến tạo đẳng cấp.
• Ví dụ: Mã 686 nghĩa là: Tắc bóng -> Chọc khe -> Tắc bóng.

Thầy Quyết muốn gửi bản kế hoạch này sang Anh. Tuy nhiên, tờ giấy A4 gửi đi chỉ đủ chỗ viết các Mã Gen có độ dài không quá ~N~ ký tự.

Yêu cầu: Thầy Quyết muốn liệt kê tất cả các Mã Gen Chiến Thắng có thể tạo ra (độ dài từ 1 đến ~N~) để HLV Amorim tha hồ lựa chọn. Hãy đếm xem có bao nhiêu mã như vậy?

Vì danh sách các vấn đề của MU dài như sớ Táo Quân, nên số lượng Mã Gen này cũng sẽ rất lớn. Hãy in ra kết quả sau khi chia lấy dư cho ~10^9 + 7~.

Dữ liệu vào (Input)

• Một dòng duy nhất chứa số nguyên dương ~N~ (~1 \le N \le 10^{18}~) – Độ dài tối đa của Mã Gen mà thầy Quyết cho phép.

Dữ liệu ra (Output)

• Một số nguyên duy nhất là số lượng Mã Gen tìm được (lấy dư theo ~10^9 + 7~).

Ví dụ minh họa

Ví dụ 1:

Ví dụ 2: