Modern Art

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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

Comments

There are no comments at the moment.