Có bao nhiêu cách đặt 3 con mã trên bàn cờ \(n\)x\(n\) sao cho trong 3 con, không có 2 con nào đang chuẩn bị ăn nhau (đang chiếu nhau)

Đầu vào

Một số nguyên dương \(n\)

Đầu ra

Kết quả bài toán chia dư \(10^9+7\)

Giới hạn

30%: \(n \le 15\)

40%: \(n \le 10^6\)

30%: \(n \le 10^{18}\)

Ví dụ

Đầu vào

3

Đầu ra

36

Giải thích

Một vài trường hợp thỏa mãn
+-+-+-+     +-+-+-+     +-+-+-+     +-+-+-+
|K|K|K|     |K|K| |     |K|K| |     |K| |K|
+-+-+-+     +-+-+-+     +-+-+-+     +-+-+-+
| | | |     |K| | |     | |K| |     | |K| |
+-+-+-+     +-+-+-+     +-+-+-+     +-+-+-+
| | | |     | | | |     | | | |     | | | |
+-+-+-+     +-+-+-+     +-+-+-+     +-+-+-+

Một vài trường hợp không thỏa mãn
+-+-+-+     +-+-+-+     +-+-+-+     +-+-+-+
|K| |K|     |K| |K|     |K| | |     |K| | |
+-+-+-+     +-+-+-+     +-+-+-+     +-+-+-+
|K| | |     | | | |     |K| |K|     |K| | |
+-+-+-+     +-+-+-+     +-+-+-+     +-+-+-+
| | | |     | |K| |     | | | |     | |K| |
+-+-+-+     +-+-+-+     +-+-+-+     +-+-+-+