题目描述

给定 $n,m,k$，和两个正整数序列 $a_{1...n},b_{1...m}$，以及一个 $k\times k$ 的 $01$ 矩阵 $s_{1...k,1...k}$。

考虑一张有向图 $G=(V,E)$，其中 $V=\{S,T\}\cup(\{0,1\}\times ([1,k]\cap\mathbb{Z})^2)$，而 $E=E_1\cup E_2\cup E_3$ 由三部分组成：

• $E_1=\{(S,(0,1,a_i)) \mid 1\le i\le n\}\cup\{((1,k,b_i),T)\mid 1\le i\le m\}$
• $E_2=\{((1,i,j),(0,i+1,j))\mid1\le i<k,1\le j\le k\}\cup \{(1,i,j),(0,i,j+1))\mid1\le i\le k,1\le j<k\}$
• $E_3=\{((0,i,j),(1,i,j))\mid 1\le i,j\le k,s_{i,j}=1\}$

简单来说，你可以看成每个格子 $(i,j),1\le i,j\le k$ 被拆成了一个入点 $(0,i,j)$ 和一个出点 $(1,i,j)$。$E_1$ 描述了 $S,T$ 与这些点之间的边，由 $a,b$ 决定；$E_2$ 描述了每个格子的出点连向它上方和右方格子的入点的边；$E_3$ 描述了每个格子的入点连向出点的边，由 $s$ 决定。

现在我们将 $G$ 看成一个网络，每条边的容量是 $1$。你需要求出以 $S$ 为源点，以 $T$ 为汇点的最大流，以及最大流的数量（两个流被认为是不同的，当且仅当存在一条边在两个流中的流量不同）。

输入格式

第一行三个正整数 $n,m,k$。

第二行 $n$ 个正整数 $1\le a_1<a_2<...<a_n\le k$。

第三行 $m$ 个正整数 $1\le b_1<b_2<...<b_m\le k$。

接下来 $k$ 行，每行一个长度为 $k$ 的 01 字符串，表示矩阵 $s$。

输出格式

输出一行两个非负整数，分别表示最大流和最大流的数量，后者对 $10^9+7$ 取模。

提示

样例见下发文件。

对于全部数据，$1\le n,m\le k\le400$。