Không biết các bài toán đa cấp có được cho vào chung một contest hay không, nhưng sau đây là một bài toán như thế:

CAO (Chief Air-conditioner Officer) của The Pyramid Company trực thuộc tập đoàn VierTech phát cho mỗi nhân viên tập sự một hình tam giác trống, gọi là tam giác cấp 0.

Khi một nhân viên mời đủ 3 người khác tham gia tập đoàn, tam giác của nhân viên đó sẽ được nâng lên cấp 1: Từ tam giác cấp 0, lấy trung điểm của 3 cạnh tam giác nối lại với nhau, chia hình cũ thành 4 hình tam giác cấp 0 nhỏ hơn.

Khi 3 người đó tiếp tục mời thêm 3 người nữa, các tam giác tiếp tục chia nhỏ như vậy, sẽ ra tam giác cấp 2 (gồm 4 hình tam giác cấp 1), cấp 3 (gồm 4 hình tam giác cấp 2), …

Lương của một nhân viên (tính bằng BTC) bằng số điểm trên tam giác mà nhân viên có. Theo hình ta thấy, lương bậc 0 là 3 BTC, bậc 1 là 6 BTC, ...

Vì là công ty đa cấp nên bạn KHÔNG CẦN BẰNG CẤP, chỉ cần có KHÁT KHAO LÀM GIÀU thì sẽ GIÀU NHANH. Cũng chẳng cần học toán, vì vậy khá nhiều nhân viên không biết lương của họ là bao nhiêu.

Một nhân viên cho bạn xem tam giác họ có, muốn nhờ bạn tính họ sẽ có bao nhiêu tiền. Tính giúp họ đê 😛

Input

• 1 dòng duy nhất gồm một số \(n\) là cấp của tam giác mà người hỏi sở hữu

Output

• Lương của người đó, tính bằng Satoshi, modulo \(10^9+7\)

Example

2

15

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n \le 20\)
• Subtask \(2\) (\(45\%\) số điểm): \(n \le 10^6\)
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 10^{18}\)