27234번 - 컵 쌓기

문제

스포츠스태킹은 $N$개의 컵을 다양한 방법으로 빠르게 쌓는 스포츠 경기다. BOJ 스포츠스태킹 협회의 회장 한나는 이번에 새롭게 출시한 빨간 컵의 판매량을 늘리기 위해 새로운 스포츠스태킹 종목을 도입하고자 한다. (문제의 그림에서 빨간 컵은 가로줄이 그려져 있는 컵이다.) 그 규칙은 다음과 같다.

참가자는 빨간 컵 $N$개와 파란 컵 $N$개를 준비한다. 참가자는 이 중 $N$개의 컵을 쌓아서 규칙에 맞는 배치를 아무거나 만들어야 한다. 컵을 쌓는 규칙은 다음과 같다.

• 맨 아랫층에는 컵이 일렬로 연속해 있어야 한다.
• 두 이웃한 컵의 중앙 위쪽에 다른 컵을 쌓을 수 있다. 이를 반복해서 여러 층을 쌓을 수도 있다.
• 두 이웃한 컵 위에 다른 컵을 쌓으려면, 두 컵 중 적어도 하나는 빨간 컵이어야 한다.

색깔이 같은 컵끼리는 구분할 수 없다고 할 때, 컵을 쌓을 수 있는 경우의 수를 주어지는 소수 $P$로 나눈 나머지를 구하시오. 두 배치가 서로 대칭이어도, 서로 다른 배치로 센다.

입력

첫 번째 줄에 쌓을 컵의 개수를 나타내는 정수 $N$과 나누어 출력할 소수 $P$가 공백을 사이에 두고 주어진다.

출력

규칙을 만족하도록 $N$개의 컵을 쌓는 경우의 수를 $P$로 나눈 나머지를 출력한다.

제한

• 1ドル\le N\le 150$
• 2ドル\le P\le 10^9$
• P는 소수이다.

힌트

3ドル$개의 컵을 쌓는 방법은 다음 그림과 같이 14ドル$가지가 있다.