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 ~998\,244\,353~.

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 ~998\,244\,353~.

Sample Input

3 2 9
3 9 6

Sample Output

1