Preparing NOJ

Mio visits ACGN Exhibition

2000ms 262144K

Description:

One day, Mio visits an Animation Comic Game Novel (ACGN) Exhibition, and she would like to buy some presents for Ritsu.

We assure that the space of the exhibition is a $$$n \times m$$$ grid, called the grid $$$A$$$, and each cell in the grid represents a stall, only selling present $$$0$$$ or $$$1$$$. In other words, every cell of the $$$n \times m$$$ grid $$$A$$$ is filled with $$$0$$$ or $$$1$$$.

Under the control policy for containing COVID-19, there are some restrictions on visiting route.

We define a SAFE PATH as a path from the top left cell $$$(1,1)$$$, to the bottom right cell $$$(n,m)$$$, and if you are in the cell $$$(x,y)$$$, then you can only travel to the cells $$$(x+1,y)$$$ or $$$(x,y+1)$$$. Every visitor has to visit the exhibition through SAFE PATH, so does Mio.

The two paths are considered to be different if and only if at least one cell passed differs.

Mio wonders how many different SAFE PATHs, which have some $$$0$$$s and $$$1$$$s, and the number of $$$0$$$ is at least $$$p$$$, the number of $$$1$$$ is at least $$$q$$$.

Since the answer may be too large, you only need to output the result modulo $$$998244353$$$.

Input:

The first line contains four integers, $$$n$$$, $$$m$$$, $$$p$$$, $$$q$$$ ($$$1\le n,m\le 500,0\le p,q \le10000$$$).

Each of the next $$$n$$$ lines contains $$$m$$$ space separated integers $$$A_{i,j}$$$ $$$(0\le A_{i,j}\le 1)$$$, denoting the number in the cell $$$(i,j)$$$ of the grid $$$A$$$.

Output:

Print a single integer, denoting the answer to the question, modulo $$$998244353$$$.

Sample Input:

2 2 1 1
0 0
1 1

Sample Output:

2

Sample Input:

3 3 2 0
0 0 1
0 0 1
1 0 0

Sample Output:

6

Info

CodeForces Gym

Provider CodeForces Gym

Origin 2021 Jiangxi Provincial Collegiate Programming Contest

Code GYM103366A

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/25/2021 22:31:43

Related

Nothing Yet