P14476 Matrix Painting

Elfin likes painting. One day, she started studying how to paint matrices. More specifically, Elfin wants to paint an $n \times n$ $01$ matrix. She starts from an all-zero matrix, and each time she can choose one row or one column to paint. If she chooses row $i$, she adds $1$ to all entries in columns $1$ to $a_i$ of that row. If she chooses column $i$, she adds $1$ to all entries in rows $1$ to $b_i$ of that column. She will not paint any cell more than once, because then the value in that cell would become greater than $1$. Here, $\{a_i\}$ and $\{b_i\}$ are two sequences of length $n$. Elfin also has an $n \times n$ draft matrix, whose entries may be $0$, $1$, or the character `?`. If a cell in the draft matrix is $0$ or $1$, then the corresponding cell in the matrix she paints must be that value. If a cell is `?`, then there is no restriction on that cell. Now Elfin wants to know how many different $01$ matrices she can paint. Two matrices are considered different if and only if there exists at least one cell where their values differ. Since the answer may be very large, output it modulo $10^9 + 7$.

**Note: Due to Luogu's judging limitations, when submitting this problem on Luogu, please use standard input/output. Do not use file input/output.** The first line contains a positive integer $n$. The next line contains $n$ non-negative integers, representing $a_i$. The next line contains $n$ non-negative integers, representing $b_i$. The next $n$ lines each contain a string of length $n$, representing the given draft matrix.

Output one integer, the answer.

### Sample Explanation 1 There are $2$ possible matrices: ``` 111 011 011 011 001 001 ``` ### Sample Explanation 2 No matrix satisfies the requirements. ### Constraints All testdata satisfy: $1 \leq n \leq 5000$, $0 \leq a_i, b_i \leq n$, and each element in the draft matrix $\in \{0, 1, ?\}$. ::cute-table{tuack} | Test Point ID | $n \leq$ | Special Property | | :--: | :--: | :--: | | $1 \sim 3$ | $8$ | — | | $4 \sim 6$ | $20$ | — | | $7 \sim 9$ | $100$ | — | | $10 \sim 13$ | $500$ | — | | $14 \sim 17$ | $5000$ | $a_1 = 0$ | | $18 \sim 21$ | $5000$ | $a_i, b_i \leq i$ | | $22 \sim 25$ | $5000$ | — | For each group of test points, the first two test points satisfy: the given matrix contains only question marks. Translated by ChatGPT 5