{"raw_statement":[{"iden":"problem statement","content":"> **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)$.\n> You will now perform the following operation for $i=1,2,\\dots,N$:\n> \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.\n> \n> Find the minimum possible value of the maximum value of $X$ at the end of the operations.\n\nYou 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$."},{"iden":"constraints","content":"*   $1 \\le N \\le 100$\n*   $1 \\le M \\le 10^{18}$\n*   $9 \\times 10^8 \\le P \\le 10^9$\n*   $P$ is prime."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$ $P$"},{"iden":"sample input 1","content":"3 3 998244353"},{"iden":"sample output 1","content":"13\n\nFor example, we solve the **Optimization Problem** for $A=(1,0,2)$. Here is a possible sequence of operations:\n\n*   For $i = 1$, let $v = 1$. $X$ becomes $(1,0,0,0)$.\n*   For $i = 2$, let $v = 0$. $X$ remains $(1,0,0,0)$.\n*   For $i = 3$, let $v = 1$. $X$ becomes $(1,0,1,1)$.\n\nSince the maximum value of $X$ cannot be made $0$ or less, the answer is $1$.\nThere are six other sequences with answer $1$ and three sequences with answer $2$, so the sum is $13$."},{"iden":"sample input 2","content":"10 135 998244353"},{"iden":"sample output 2","content":"679877945"},{"iden":"sample input 3","content":"100 1000000000000000000 924844033"},{"iden":"sample output 3","content":"789282612"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}