M. Machine for picking shells
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Shell Beach, located in Guarujá, is known for having many shells. A group of local scientists has developed a robot capable of collecting shells from the seabed. The robot first identifies a sequence of $$$N$$$ shells in a line on the seabed, assigns positions from $$$1$$$ to $$$N$$$ to them, and detects the type of each shell, represented by some integer from $$$1$$$ to $$$N$$$.

After this, the robot chooses the first shell to collect. As soon as the robot reaches the seabed and collects the first shell, all shells in positions with a difference less than or equal to $$$K$$$ compared to the position of the first shell end up being covered by sand due to the impact of the robot's landing. For example, if $$$K = 2$$$ and the position of the first shell is $$$5$$$, the shells in positions $$$3$$$, $$$4$$$, $$$6$$$, and $$$7$$$ gets covered by sand.

After collecting the first shell, the robot can only collect the uncovered shells that are in a position less than the position of the first shell, freely deciding which of these possible shells to take or not.

Now this group of scientists is curious about how many different sets can be collected by this robot. Two shells of the same type can be considered indistinguishable, meaning that two sets of shells are different if and only if there is some type of shell with a different quantity between the two sets. Since the answer can be very large, print the answer modulo $$$998244353$$$.

Input

The first line contains two integers $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ and $$$K$$$ $$$(0 \leq K \lt N)$$$ which are respectively the number of shells in line detected by the robot and the integer $$$K$$$ that indicates the position difference at which the shells are covered when the robot collects the first shell. The second line contains $$$N$$$ integers $$$T_i$$$ $$$(1 \leq T_i \leq N)$$$ indicating the types of shells found by the robot in order of their positions from $$$1$$$ to $$$N$$$.

Output

The output should contain only one integer equal to the number of different sets of shells that can be collected by the robot in a single trip to the sea modulo $$$998244353$$$.

Examples
Input
3 2
1 2 3
Output
3
Input
7 3
1 2 3 1 2 3 3
Output
11
Note

Explanation of example 1:

Possible sets: $$$\{1\}$$$, $$$\{2\}$$$, $$$\{3\}$$$. Only the first shell can be taken; the others get covered.

Explanation of example 2: Possible sets: $$$\{1\}$$$, $$$\{1, 2\}$$$, $$$\{1, 2, 3\}$$$, $$$\{1, 2, 3, 3\}$$$, $$$\{1, 3\}$$$, $$$\{1, 3, 3\}$$$, $$$\{2\}$$$, $$$\{2, 3\}$$$, $$$\{2, 3, 3\}$$$, $$$\{3\}$$$, $$$\{3, 3\}$$$.