Tứ diện

Cho một tứ diện có bốn đỉnh được đặt tên $A$, $B$, $C$, $D$. Bốn đỉnh này tạo thành đồ thị đầy đủ $K_4$: giữa hai đỉnh bất kỳ luôn có đúng một cạnh nối.

Một con kiến đang đứng ở đỉnh $D$. Tại mỗi bước, kiến di chuyển từ đỉnh hiện tại sang một đỉnh kề bất kỳ (kiến không được đứng yên).

Hãy đếm số cách di chuyển khác nhau để kiến đi từ đỉnh $D$ về lại đỉnh $D$ sau đúng $n$ bước. Vì số lượng có thể rất lớn, in ra kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$ — số bước di chuyển.

Dữ liệu ra

In ra số đường đi cyclic có độ dài $n$ từ $D$ về $D$, lấy modulo ${10}^9+7$.

Ràng buộc

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

Ví dụ