题目描述

给定一个严格递增的正整数序列：

$$a_1<a_2<\cdots<a_n$$

你需要统计有多少个序列 $p_1,p_2,\ldots,p_n$ 满足：

1. $p$ 是 $a$ 的一个排列，即 $p$ 中恰好包含 $a_1,a_2,\ldots,a_n$ 各一次；
2. 对任意 $1\le i<n$，都有

$$|p_i-p_{i+1}|\ne k$$

答案对 $998244353$ 取模。

输入格式

第一行两个正整数 $n,k$，分别表示序列长度和限制参数。

第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行一个整数，表示满足条件的排列数量，答案对 $998244353$ 取模。

样例 1

输入

4 1
1 2 3 4

输出

2

解释

只有下列两种排列满足相邻元素差的绝对值不等于 $1$：

3 1 4 2
2 4 1 3

样例 2

输入

7 2
1 2 3 4 6 7 8

输出

1272

数据范围与子任务

保证：

$$n\le 5\times 10^3,\quad k\le 10^6,\quad a_i\le 10^9$$

子任务	分值	限制
1	20	$n\le 10$
2	30	$n\le 400$
3	20	$n\le 1000$
4	30	无特殊限制