Given a sequence of positive integers $a_1, a_2, \dots, a_n$ ($a_1 < a_2 < \dots < a_n$), find the number of permutations $\{p_n\}$ of this sequence such that for all $1 \leq i \leq n-1$, $|p_i - p_{i+1}| \neq k$. Output the answer modulo $998244353$.

Input

The first line contains two positive integers $n$ and $k$, representing the number of elements in the sequence and the value of $k$ in the constraint, respectively.

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

Output

Output a single integer representing the number of permutations that satisfy the requirements.

Examples

Input 1

4 1
1 2 3 4

Output 1

2

Note 1

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

Input 2

7 2
1 2 3 4 6 7 8

Output 2

1272

Constraints

It is guaranteed that $n \leq 5 \times 10^3$, $k \leq 10^6$, and $a_i \leq 10^9$.

• Subtask 1 (20 pts): $n \leq 10$.
• Subtask 2 (30 pts): $n \leq 400$.
• Subtask 3 (20 pts): $n \leq 1000$.
• Subtask 4 (30 pts): No additional constraints.