Background

Gauss was bored for the second time.

高斯第二次无聊。

Description

Given an integer sequence {a} of length n and a fixed value k, Gaussian would like to know how many non-empty sequences in {a} satisfy that the absolute value of the difference between any two adjacent elements is less than k. Because the answer may be very large, you need to output the result after the answer is modulized to 998244353.

给定一个长度为 n 的整数序列 {a}，以及一个定值 k，高斯想知道，{a} 中有多少个非空子序列，满足任意 2 个相邻元素之差的绝对值均小于 k。
因为答案可能很大，所以你需要输出答案对998244353取模后的结果。

Format

Input

A total of two rows, the first row of 2 integers n and k,
The second row has a total of n numbers, and the I number is ai.

共两行，第一行2个整数n和k，
第二行共n个数，第i个数为ai。

Output

A total of two rows, the first row of 2 integers n and k, The second row has a total of n numbers, and the I number is ai.

输出共一个数，表示答案。

Sample 1

Input

3 2
-1 0 1

Output

6

Sample explanation

{−1},{0},{1},{−1,0},{0,1},{−1,0,1}{−1},{0},{1},{−1,0},{0,1},{−1,0,1} 均为合法的序列

Limitation

对于 40% 的数据，1≤n≤103。
对于 100% 的数据，1≤n≤106,|ai|≤106,0≤k≤10。

Source

Amorphophallus Orz Group