Tèo nuôi \(N\) con chuồn chuồn, vì tinh nghịch nên Tèo dán lên mỗi con chuồn chuồn một số \(X (1 \le X \le 3)\). Sau khi dán xong, Tèo bỗng nhiên nãy ra một câu hỏi: "Có bao nhiêu cách dán các số lên các con chuồn chuồn sao cho tổng các số sau khi dán chia hết cho 3 ?".

Vì có quá nhiều con chuồn chuồn nên Tèo nhờ bạn giúp. Bạn hãy giúp Tèo giải câu hỏi trên nhé.

Input

• Gồm một dòng duy nhất chứa số nguyên \(N (1 \leq N \le 10^{18})\).

Output

• Gồm một số nguyên duy nhất là kết quả bài toán (Kết quả lấy phần dư cho \(10^9 + 7\)).

Example

2 

3