You are a modern artist looking to create modern art in modern ways.

You will paint on a canvas $N$ tiles long. Each tile can take on two colours: white or red. Initially, all tiles are white.

The paintbrush you'll be using is modern as well. Painting a white tile will turn it red, and painting a red tile will turn it white. Since it's the modern trend, you are only willing to make strokes that paint exactly $K$ consecutive tiles. You can make as many strokes as you'd like.

Even the value of modern art is determined in modern ways. The $i$-th tile from the left has a value of $w_i$, and the value of a painting is the sum of the values of all the red tiles. Being a curious artist, you wonder: of all the final paintings you can create, how many have a value of $Y$? Since this number may be huge, please output it modulo $998244353$.

Constraints

$1\le N\le {10}^4$

$1\le K\le min(N,20)$

$0\le w_i,Y\le {10}^3$

Subtask 1 [5%]

$K=1$

Subtask 2 [95%]

No additional constraints.

Input Specification

The first line will contain three integers, $N$, $K$, and $Y$.

The next line will contain $N$ space-separated integers, the $i$-th of which represents $w_i$.

Output Specification

Output the number of paintings you can create with value equal to $Y$, modulo $998244353$.

Sample Input

3 2 9
3 9 6

Sample Output

1