#P18222. NonZero PrefSuf Sums

NonZero PrefSuf Sums

NonZero PrefSuf Sums

Shrek 给出了下面这个形式化的问题。

给定整数 n,mn,m 和大素数 pp,求满足以下条件的整数数组 [a1,a2,…,an][a_1,a_2,\ldots,a_n] 的个数:

  1. 对所有 1≤i≤n1\le i\le n,都有 ∣ai∣≤m|a_i|\le m。
  2. 存在一个由数组 aa 的全部元素重排得到的数组 [b1,b2,…,bn][b_1,b_2,\ldots,b_n],使得:
    • 对所有 1≤k≤n1\le k\le n,b1+b2+⋯+bk≠0b_1+b_2+\cdots+b_k\ne0;
    • 对所有 1≤k≤n1\le k\le n,bk+bk+1+⋯+bn≠0b_k+b_{k+1}+\cdots+b_n\ne0。

答案对 pp 取模。只要存在一种符合要求的重排,原数组就计入答案一次;不同下标上的元素取值不同便是不同数组。本题不要求输出重排。

输入格式

仅一行,包含三个整数 n,m,pn,m,p。只有一组数据。

输出格式

输出一个整数,表示所求数组个数对 pp 取模的结果。

数据范围

  • 2≤n≤1002\le n\le100;
  • 1≤m≤1001\le m\le100;
  • 108<p<10910^8<p<10^9,保证 pp 为素数。

样例 1

2 1 998244353
2

样例 2

69 42 696969697
378553557

样例说明

样例 1 中共有九个可能的数组:$[-1,-1],[-1,0],[-1,1],[0,-1],[0,0],[0,1],[1,-1],[1,0],[1,1]$。只有 [−1,−1][-1,-1] 和 [1,1][1,1] 满足条件。