Stacking Cups

Time limit2sMemory limit1024 MB

Summary

Count the valid stacks of exactly N red and blue cups, where each cup on top sits on two neighbors with at least one red, modulo prime P.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

Sports stacking is a sport in which $N$ cups are stacked quickly in various ways. Hanna, the president of the sports stacking association, wants to boost sales of a newly released red cup by introducing a new sports stacking event. (In the figure, the red cups are the ones with horizontal stripes.) The rules are as follows.

Each participant prepares $N$ red cups and $N$ blue cups. From these, the participant must build any arrangement that follows the rules using $N$ cups. The rules for stacking cups are as follows.

The bottom layer must consist of cups placed in one continuous row.
A cup can be placed above the center of two adjacent cups. This can be repeated to build several layers.
To place a cup on top of two adjacent cups, at least one of those two cups must be red.

Cups of the same color cannot be told apart. Find the number of ways to stack the cups, modulo the given prime $P$ . Two arrangements that are mirror images of each other are counted as different.

Input

The first line contains the integer $N$ , the number of cups to stack, and the prime $P$ to divide by, separated by a space.

Output

Print the number of ways to stack $N$ cups that satisfy the rules, modulo $P$ .

Constraints

$1\le N\le 150$
$2\le P\le 10^9$
$P$ is prime.

Hint

There are $14$ ways to stack $3$ cups, as shown in the following figure.

Examples3

Example 1
Input
```
3 998244353
```
Expected output
```
14
```
Example 2
Input
```
5 998244353
```
Expected output
```
124
```
Example 3
Input
```
7 998244353
```
Expected output
```
1248
```