예쁜 수열

오늘은 수열의 날이다! 수학 선생님은 칠판에 1부터 N까지의 서로 다른 수 N개로 이루어진 수열 몇 개를 적고, 학생들에게 이 수열들이 특별한 성질을 가진다고 말했다. 학생 중 한 명인 Deni는 고민 끝에 그 성질을 알아냈다. 칠판에 적힌 모든 수열에는 (x, x + 1) 꼴의 인접한 두 수가 적어도 한 쌍 있었다. Deni는 기뻐서 이런 수열을 예쁘다고 불렀다. 예를 들어 N = 4일 때 수열 3, 1, 2, 4와 2, 3, 4, 1은 예쁘지만, 수열 2, 4, 1, 3과 4, 3, 2, 1은 예쁘지 않다. 그 후 수학 선생님은 Deni에게 더 어려운 문제를 냈다. 1부터 N까지의 서로 다른 수 N개로 만들 수 있는 모든 예쁜 수열의 개수를 구하라는 것이었다. 너무 어려워서 Deni는 수업이 끝날 때까지 답을 찾지 못했다. 당신은 Deni의 친구이고, Deni를 도와주려 한다.

주어진 N에 대해 예쁜 수열의 개수를 구하는 프로그램을 작성하라. 이 수는 매우 클 수 있으므로 M으로 나눈 나머지를 계산해야 한다.

표준 입력의 첫째 줄에서 두 정수 N과 M을 읽는다. N은 칠판에 적힌 수열의 길이이고, M은 계산에 사용하는 모듈러스이다.

표준 출력의 한 줄에 1부터 N까지의 서로 다른 수 N개로 이루어진 예쁜 수열의 개수를 M으로 나눈 나머지를 출력한다.

• 1 ≤ N ≤ 10^18
• 2 ≤ M ≤ 10^7