#P18222. NonZero PrefSuf Sums
NonZero PrefSuf Sums
NonZero PrefSuf Sums
Shrek 给出了下面这个形式化的问题。
给定整数 和大素数 ,求满足以下条件的整数数组 的个数:
- 对所有 ,都有 。
- 存在一个由数组 的全部元素重排得到的数组 ,使得:
- 对所有 ,;
- 对所有 ,。
答案对 取模。只要存在一种符合要求的重排,原数组就计入答案一次;不同下标上的元素取值不同便是不同数组。本题不要求输出重排。
输入格式
仅一行,包含三个整数 。只有一组数据。
输出格式
输出一个整数,表示所求数组个数对 取模的结果。
数据范围
- ;
- ;
- ,保证 为素数。
样例 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]$。只有 和 满足条件。