Statement
Statement language
The king game is a one-player game played with a rectangular chocolate board and a chess king. First, put the king on the top-leftmost cell. Then move the king according to its movement rules, never visiting the same cell twice. The player wins if the king ends at the bottom-rightmost cell after visiting all other cells exactly once. A chess king can move to one of eight orthogonally or diagonally adjacent cells, but it cannot move out of the board.
Coco is playing the king game on a chocolate board of size . Calculate the number of ways to win the game.
Input
The first line of input contains the integer . ()
Output
Output the answer modulo .
Subtasks
Samples
Sample 1
Input
2
Output
6
Sample 2
Input
6
Output
11563