Problem Statement

Optimization Problem

You are given a length-$N$ sequence of non-negative integers $A=(A_1,A_2,\dots,A_N)$. Also, there is a length-$N+1$ sequence of non-negative integers $X=(0,0,\dots,0)$.

You will now perform the following operation for $i=1,2,\dots,N$:

• Choose an integer $v$ satisfying $0 \le v \le A_i$, and add $v$ and $A_i-v$ to $X_i$ and $X_{i+1}$, respectively.

Find the minimum possible value of the maximum value of $X$ at the end of the operations.

You are given positive integers $N$, $M$, and a prime number $P$. Find the sum, modulo $P$, of the answers to the Optimization Problem for all sequences $A=(A_1,A_2,\dots,A_N)$ of non-negative integers with length $N$ and sum $M$.

Constraints

• $1 \le N \le 100$
• $1 \le M \le 10^{18}$
• $9 \times 10^8 \le P \le 10^9$
• $P$ is prime.

Input

The input is given from Standard Input in the following format:

N M P

Output

Output the sum, modulo $P$, of the answers to the Optimization Problem.