Problem Description

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$.

Input Format

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 Format

Output one integer, the answer.

3
1 2 3
1 2 3
?11
???
?0?

2

1
0
0
1

0

Hint

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}

For each group of test points, the first two test points satisfy: the given matrix contains only question marks.

Translated by ChatGPT 5