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| |
+-+-+-+     +-+-+-+     +-+-+-+     +-+-+-+