체스판

바이테아사르(Byteasar)는 체스 퍼즐을 좋아합니다. 그는 오랫동안 체스 잡지를 구독해 왔고, 최신 호에는 다음과 같은 퍼즐이 실려 있습니다.

$n \times n$ 크기의 체스판이 주어진다. 이 체스판 위에 룩(rook) $n$개를 놓되, 어떤 두 룩도 서로 공격하지 않고(즉 같은 행이나 같은 열을 공유하지 않고), 모든 $i$에 대해 $i$번째 룩이 $i$번째 행에도 $i$번째 열에도 놓이지 않도록 하는 방법은 몇 가지인가? 룩과 행, 열은 모두 $1$부터 $n$까지 번호가 매겨져 있다. 답은 $m$으로 나눈 나머지로 구한다.

바이테아사르에게 "13수 만에 체크메이트" 같은 퍼즐은 식은 죽 먹기지만, 이 새로운 유형의 퍼즐은 무척 어려워 보입니다. 그를 도와줄 수 있나요?

첫째 줄에 두 정수 $n$과 $m$이 공백으로 구분되어 주어진다 ($1 \le n \le 10^{18}$, $1 \le m \le 10^{6}$).

가능한 룩 배치의 수를 $m$으로 나눈 나머지를 한 줄에 출력한다.