Cho một hàng có \(n\) quả bóng màu trắng, được đánh số thứ tự lần lượt từ \(1\) đến \(n\). Alice tô mỗi quả bóng bởi một trong ba màu xanh, đỏ, vàng sao cho không có hai quả bóng nào cạnh nhau cùng được tô màu đỏ.

Viết chương trình tính số khả năng khác nhau về thứ tự màu của dãy bóng mà Alice sẽ tô. Nếu kết quả có giá trị lớn thì đưa ra giá trị theo modulo \(10^9 + 7\).

Input Specification

Gồm số nguyên dương \(n\) được ghi trên một dòng duy nhất.

Output Specification

In ra kết quả trên một dòng.

Constraints

\(n \leq 10^6\)

Input Sample

2

Output Sample

8