Chú lùn và đồng xu

Có $3n$ chú lùn ngồi quanh một bàn tròn. Mỗi chú lùn được nhận một số đồng xu từ $1$ đến $3$. Các vị trí được đánh số từ $0$ đến $3n-1$ theo thứ tự trên vòng tròn; chú lùn ngồi ở vị trí $i$ nhận $a_i$ đồng xu.

Cách phân phối được gọi là hợp lệ nếu tồn tại chỉ số $i$ ($0\le i<n$) sao cho:

$$a_i+a_{i+n}+a_{i+2n}\ne 6$$

Hãy đếm số cách chọn các giá trị $a_i$ để cách phân phối hợp lệ. Vì kết quả có thể rất lớn, in ra phần dư của nó khi chia cho ${10}^9+7$.

Hai cách phân phối $a$ và $b$ được coi là khác nhau nếu tồn tại chỉ số $i$ ($0\le i<3n$) sao cho $a_i\ne b_i$.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$.

Dữ liệu ra

In ra một số nguyên duy nhất: số cách phân phối hợp lệ, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^5$

Ví dụ