Johnny 学会了玩井字棋。他非常喜欢这个游戏，以至于决定将其推广到更大的棋盘上。显然他不知道五子棋，因为在他的推广中，要获胜需要用自己的符号填满整整一行、一列或两条主对角线之一。为他的游戏设计策略看起来很困难，因此 Johnny 决定解决一个更简单的问题——有多少种大小为 $n \times n$ 的平局棋盘？也就是说，棋盘完全由圈和叉填满，且没有任何一行、一列或两条主对角线之一完全由同一种符号填满。Johnny 想要解决该问题最基础的版本，因此他允许圈和叉的比例是任意的，并且不将通过旋转或对称可以得到的棋盘视为同一种。即使在这个基础版本中，问题似乎也很困难，请帮助 Johnny 解决它！

输入格式

输入仅包含一行，有两个整数 $n$ 和 $p$（$1 \le n \le 300$，$2 \le p \le 10^9 + 9$），中间用单个空格分隔，其中 $n$ 是 Johnny 棋盘的大小，$p$ 是一个质数。

输出格式

输出仅包含一行，即一个整数——所有完全由圈和叉填满且没有任何一行、一列或两条主对角线之一完全由同一种符号填满的 $n \times n$ 棋盘总数模 $p$ 的余数。

样例

输入样例 1

3 101

输出样例 1

32

输入样例 2

4 3

输出样例 2

2