题意
有一个大小为 $n \times n$ 的棋盘，左上角的位置为 $(0,0)$，右下角的位置为 $(n-1,n-1)$。
在这个棋盘上，两颗棋 $(x_1,y_1),(x_2,y_2)$ 是相邻的，当且仅当 $x_1=x_2,y_1\equiv y_2 + 1 \pmod n$，或 $y_2\equiv y_1 + 1 \pmod n$
你需要在上面放 $k$ 个不重叠的棋子，使得任意两颗棋子不相邻。求方案数，对 $p^2$ 取模，$p$ 为素数。
输入格式
一行三个整数，$n,k,p$
输出格式
一行一个整数，表示答案。
数据范围
$n \leq 10^9,k \leq \min(10^5 \times n,n \times \frac{n}{2})$
$10^7 \leq p \leq 10^7 + 10^3$，保证 $p$ 为质数。