Bài toán Mã đi tuần có lẽ đã rất quen thuộc với các bạn yêu thích bộ môn Cờ Vua và Toán học.

Viết chương trình tính số cách để quân Mã trên bàn cờ \(N\times N\) (\(N\) chẵn và \(2\leq N\leq20\)) đi từ ô góc trên bên trái, qua tất cả các ô trên bàn cờ mỗi ô đúng \(1\) lần và kết thúc tại ô góc dưới bên phải. Quân mã di chuyển theo hình chữ L (giữa hai góc của hình chữ nhật có kích thước \(2\times3\)).

Kết quả có thể rất lớn nên bạn chỉ cần in ra số dư của nó khi chia cho \(10^9+7\).

Input

• Gồm một số nguyên dương \(N\): kích thước bàn cờ.

Output

• Số cách đi của quân Mã mod \(10^9+7\).

Ví dụ

Sample input

2

Sample output

0

Giải thích

Vì kích thước bàn cờ \(2\times2\) quá nhỏ nên quân mã không thể di chuyển. Vì vậy có \(0\) đường đi thỏa mãn yêu cầu bài toán.