선

Johnny는 틱택토를 배웠다. 이 게임을 너무 좋아한 나머지 더 큰 판으로 일반화하기로 했다. Johnny가 오목을 모르는 것은 분명하다. 그가 일반화한 게임에서는 자기 기호로 한 줄(세로, 가로 또는 두 주대각선 중 하나)을 모두 채워야 이기기 때문이다. 이 게임의 전략을 세우는 일은 어려워 보여서 Johnny는 더 단순한 문제를 다루기로 했다. 크기가 $n \times n$인 무승부 판, 즉 O와 X로 완전히 채워져 있고 어떤 줄(세로, 가로 또는 두 주대각선 중 하나)도 한 기호로만 채워지지 않은 판은 몇 개인가? Johnny는 문제의 가장 기본적인 변형을 풀고 싶어서 O와 X의 비율을 임의로 허용하고, 회전이나 대칭으로 얻을 수 있는 판도 서로 다른 판으로 센다. 이 기본 변형에서도 문제는 어려워 보이니, Johnny를 도와 이 문제를 풀어라!

입력은 한 줄이며, 두 정수 $n$과 $p$가 공백 하나를 사이에 두고 주어진다. ($1 \le n \le 300$, $2 \le p \le 10^9+9$) $n$은 Johnny의 판 크기이고 $p$는 소수이다.

출력도 한 줄이며, 정수 하나를 출력한다. 이는 O와 X로 완전히 채워져 있고 가로, 세로 또는 두 주대각선 중 어느 줄도 한 기호로만 채워지지 않은 모든 $n \times n$ 판의 수를 $p$로 나눈 나머지이다.