AT_agc075_e [AGC075E] Many Optimization Problems

> **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 $ .

The input is given from Standard Input in the following format: > $ N $ $ M $ $ P $

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

### Sample Explanation 1 For example, we solve the **Optimization Problem** for $ A=(1,0,2) $ . Here is a possible sequence of operations: - For $ i = 1 $ , let $ v = 1 $ . $ X $ becomes $ (1,0,0,0) $ . - For $ i = 2 $ , let $ v = 0 $ . $ X $ remains $ (1,0,0,0) $ . - For $ i = 3 $ , let $ v = 1 $ . $ X $ becomes $ (1,0,1,1) $ . Since the maximum value of $ X $ cannot be made $ 0 $ or less, the answer is $ 1 $ . There are six other sequences with answer $ 1 $ and three sequences with answer $ 2 $ , so the sum is $ 13 $ . ### Constraints - $ 1 \le N \le 100 $ - $ 1 \le M \le 10^{18} $ - $ 9 \times 10^8 \le P \le 10^9 $ - $ P $ is prime.