Busy Beaver는 $N$개의 음이 아닌 정수로 이루어진 배열 $A_1, A_2, \dots, A_N$이 다음 조건을 만족할 때 이를 unavoidable하다고 부릅니다:

• 모든 $i$ ($1 \le i \le N$)에 대하여 $B_i + C_i = A_i$를 만족하는 음이 아닌 정수 배열 $(B_1, B_2, \dots, B_N)$과 $(C_1, C_2, \dots, C_N)$의 모든 쌍에 대하여, 다음 조건이 성립합니다:
  • 모든 $i$에 대하여 $X_i = B_i$ 또는 $X_i = C_i$를 만족하는 배열 $(X_1, X_2, \dots, X_N)$이 존재하여 $X_1 \oplus X_2 \oplus \dots \oplus X_N = 0$이 성립합니다.

여기서 $\oplus$는 비트 단위 XOR 연산을 나타냅니다.

$N$과 $K$가 주어집니다. 모든 $i$에 대하여 $0 \le A_i \le 2^K - 1$인 길이 $N$의 unavoidable한 배열의 개수를 구하십시오. 이 수는 매우 클 수 있으므로, 소수 $P$로 나눈 나머지를 출력하십시오.

입력

각 테스트 케이스의 유일한 줄에는 세 정수 $N, K, P$ ($1 \le N, K \le 100$, $10^8 < P < 10^9$, $P$는 소수)가 주어집니다.

출력

모든 $i$에 대하여 $0 \le A_i \le 2^K - 1$인 길이 $N$의 unavoidable한 배열의 개수를 나타내는 정수 하나를 출력하십시오.

예제

입력 1

10 1 111111113

출력 1

1024

입력 2

14 2 263652251

출력 2

237

입력 3

100 100 998244353

출력 3

914574519

참고

첫 번째 예제에서, $\{0, 1\}$의 원소로 이루어진 모든 배열은 unavoidable합니다(그 이유를 직접 확인해 보십시오). 따라서 길이가 10인 배열은 총 $2^{10}$개가 존재합니다.