MP3 플레이어

바샤는 얼마 전 새 MP3 플레이어 doPi Shuffle을 샀다. 이 플레이어에는 바샤가 써 본 다른 기기와 달리 재생 목록(플레이리스트)의 곡 순서를 섞는 "셔플" 기능이 있다.

바샤는 좋아하는 곡 $n$개를 플레이어에 넣었다. 그 곡들은 오랫동안 컴퓨터에서 들어서 재생 목록의 순서를 잘 기억하고 있다.

플레이어는 곡을 무작위 순서로 바꿔 놓았다. 재생 목록을 여러 번 들어 본 바샤는 원래 목록에서 바로 이어져 있던 두 곡이 새 목록에서는 이어져 있지 않다는 것을 알았다. 이런 상황이 얼마나 자주 가능한지 궁금해졌다.

컴퓨터의 재생 목록 순서대로 곡에 1부터 $n$까지 번호를 붙이자. 번호가 연속된 두 곡이 서로 옆에 오지 않도록 곡을 다시 배열하는 방법의 수를 구하는 프로그램을 작성하라. 이 수는 매우 클 수 있으므로 $m$으로 나눈 나머지를 출력한다.

입력 파일에는 두 정수 $n$과 $m$이 주어진다 ($2 \le n \le 2000$, $2 \le m \le 10^9$).

조건을 만족하는 배열 방법의 수를 $m$으로 나눈 나머지를 출력한다.