Given a sequence of positive integers $a_1, a_2, \dots, a_n$ ($a_1 < a_2 < \dots < a_n$), where all elements are distinct.

Find the number of permutations $p_1, \dots, p_n$ of $1 \sim n$ such that for all $1 \le i \le n-1$, $|a_{p_i} - a_{p_{i+1}}| \ne k$. Output the answer modulo $998244353$.

Input

The first line contains two integers $n$ and $k$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output

Output a single integer representing the answer.

Examples

Input 1

4 1
1 2 3 4

Output 1

2

Note 1

The permutations $3, 1, 4, 2$ and $2, 4, 1, 3$ satisfy the condition.

Input 2

(See provided files)

Output 2

(See provided files)

Constraints

For all test cases:

• $1 \le n \le 5 \times 10^3$
• $1 \le k \le 10^6$
• $1 \le a_i \le 10^9$