Lines

Johnny has learned to play tic-tac-toe. He likes the game so much that he decided to generalize it to larger boards. He clearly does not know gomoku, because in his generalization you win by filling a whole line (vertical, horizontal, or one of the two main diagonals) with your symbol. Designing a strategy for his game looks difficult, so Johnny decided to handle a simpler problem: how many tie boards of size $n \times n$ are there, that is, boards completely filled with O and X such that no line (vertical, horizontal, or one of the two main diagonals) is filled with a single symbol. Johnny wants to solve the most basic variant of the problem, so he allows any proportion of O and X and does not treat boards that can be obtained by rotation or reflection as the same. Even in this basic variant the problem seems difficult, so help Johnny solve it!

The first and only line contains two integers $n$ and $p$ ($1 \le n \le 300$, $2 \le p \le 10^9+9$), separated by a single space. $n$ is the size of Johnny's board and $p$ is a prime number.

Print one integer on the first and only line: the remainder modulo $p$ of the number of all $n \times n$ boards completely filled with O and X in which no line (horizontal, vertical, or one of the two main diagonals) is filled with a single symbol.