Anh Sơn thích bán đồ đa cấp.

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.

Anh Sơn cho bạn xem tam giác họ có, muốn nhờ bạn tính xem anh Sơn sẽ có bao nhiêu tiền. Tính giúp anh Sơn đê :P

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 (n < 10^18)

Output:

• Lương của người đó, tính bằng Satoshi, modulo 109+7