컵 쌓기

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

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

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

같은 색 컵끼리는 구분할 수 없다. 컵을 쌓는 경우의 수를 주어진 소수 $P$로 나눈 나머지를 구하라. 서로 대칭인 두 배치도 서로 다른 배치로 센다.

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

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

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

컵 3개를 쌓는 방법은 다음 그림과 같이 14가지가 있다.