📖 Bài giảng & lời giải: đây là Bài tập 8 trong bài giảng Thuật toán qua trò chơi 1: Tháp Hà Nội trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Tháp có $2n$ đĩa: với mỗi kích thước $1, 2, \ldots, n$ có hai đĩa, một trắng một đen. Ban đầu cả tháp ở cột 1, xếp theo kích thước giảm dần từ dưới lên, và với mỗi kích thước thì đĩa đen nằm ngay dưới đĩa trắng.

Luật chơi như Tháp Hà Nội (3 cột, mỗi nước chuyển một đĩa trên cùng của một cột sang đỉnh cột khác, không đặt đĩa lớn lên đĩa nhỏ hơn), nhưng hai đĩa cùng kích thước được đặt lên nhau theo thứ tự nào cũng được.

Cần chuyển cả tháp sang cột 3 sao cho cuối cùng, với mọi kích thước, đĩa trắng vẫn nằm trên đĩa đen (đúng như ban đầu). Hãy tính số nước ít nhất, chia lấy dư cho $10^9 + 7$.

Dữ liệu vào

Một số nguyên $n$ ($1 \le n \le 10^{18}$).

Kết quả

In ra số nước ít nhất chia lấy dư cho $10^9 + 7$.

Sample Input

2

Sample Output

11