题目描述
给一个正整数序列 a1,a2,...,an(a1<a2<...<an),求有多少种这个序列的排列 {pn} 满足对所有 1≤i≤n−1,有 |pi−pi+1|≠k,答案模 998244353。
输入格式
第一行两个正整数 n,k,分别代表序列中的元素个数和限制中 k 的值。
第二行 n 个正整数 a1,a2,...,an。
输出格式
一行一个正整数,代表满足要求的排列个数。
样例输入 1
4 1 1 2 3 4
样例输出 1
2
样例解释 1
只有 3,1,4,2 和 2,4,1,3 两种排列满足条件。
样例输入 2
7 2 1 2 3 4 6 7 8
样例输出2
1272
数据范围
保证 n≤5×103,k≤106,ai≤109 。
subtask1(20pts):保证 n≤10 。
subtask2(30pts):保证 n≤400 。
subtask3(20pts):保证 n≤1000 。
subtask4(30pts):无特殊限制