题目描述

艾莉芬喜欢画画。有一天，她研究起了如何画矩阵。

具体来说，艾莉芬想画一个 $n \times n$ 的 01 矩阵。她会从一个全为 0 的矩阵开始画，每次可以选一行或者一列进行涂色。如果选择了第 $i$ 行，她会将其中第 1 到 $a_i$ 列的值都加上 1；如果选择了第 $i$ 列，她会将其中第 1 到 $b_i$ 行的值都加上 1。她不会将一个位置涂色超过一次，因为这样这个位置的值会大于 1。其中，$\{a_i\}, \{b_i\}$ 是两个长为 $n$ 的数列。

艾莉芬还有一个 $n \times n$ 的草稿矩阵，草稿矩阵中的值可能是 0、1 或者字符 ?。如果草稿矩阵中一个位置的值是 0 或 1，那么她画出的矩阵的这个位置就必须是相应的值；如果一个位置的值是 ?，那么这个位置的值就没有限制。

现在艾莉芬想知道她能画出多少种不同的 01 矩阵，两个矩阵不同当且仅当至少存在一个位置的值不同。由于这个数可能很大，只需要求出这个数对 $10^9 + 7$ 取模后的结果。

输入格式

注：由于洛谷的评测限制，在洛谷上提交本题请使用标准输入输出，不要使用文件输入输出。

第一行一个正整数 $n$；

之后一行 $n$ 个非负整数表示 $a_i$；

之后一行 $n$ 个非负整数表示 $b_i$；

之后 $n$ 行，每行一个长度为 $n$ 的字符串，表示题中给定的草稿矩阵。

输出格式

一行一个整数表示答案。

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

2

1
0
0
1

0

提示

【样例解释 1】

可能的矩阵为以下 2 种：

111 011
011 011
001 001

【样例解释 2】

不存在符合要求的矩阵。

【测试点约束】

所有测试数据均满足：$1 \leq n \leq 5000$，$0 \leq a_i, b_i \leq n$，草稿矩阵中的元素 $\in \{0, 1, ?\}$。

::cute-table{tuack}

测试点编号	$n \leq$	特殊性质
$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$		$a_i, b_i \leq i$
$22 \sim 25$		—

每组测试点的前两个均满足：给定的矩阵仅包含问号。