{"raw_statement":[{"iden":"statement","content":"给定 $n,m,k$，和两个正整数序列 $a_{1...n},b_{1...m}$，以及一个 $k\\times k$ 的 $01$ 矩阵 $s_{1...k,1...k}$。\n\n考虑一张有向图 $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$ 由三部分组成：\n\n- $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\\}$\n- $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\\}$\n- $E_3=\\{((0,i,j),(1,i,j))\\mid 1\\le i,j\\le k,s_{i,j}=1\\}$\n\n简单来说，你可以看成每个格子 $(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$ 决定。\n\n现在我们将 $G$ 看成一个网络，每条边的容量是 $1$。你需要求出以 $S$ 为源点，以 $T$ 为汇点的最大流，以及最大流的数量（两个流被认为是不同的，当且仅当存在一条边在两个流中的流量不同）。"},{"iden":"input","content":"第一行三个正整数 $n,m,k$。\n\n第二行 $n$ 个正整数 $1\\le a_1<a_2<...<a_n\\le k$。\n\n第三行 $m$ 个正整数 $1\\le b_1<b_2<...<b_m\\le k$。\n\n接下来 $k$ 行，每行一个长度为 $k$ 的 01 字符串，表示矩阵 $s$。"},{"iden":"output","content":"输出一行两个非负整数，分别表示最大流和最大流的数量，后者对 $10^9+7$ 取模。"},{"iden":"note","content":"样例见下发文件。\n\n对于全部数据，$1\\le n,m\\le k\\le400$。\n\n| 子任务编号 | $n\\le$ | $k\\le$ |       特殊性质       | 子任务分值 |\n| :--------: | :----: | :----: | :------------------: | :--------: |\n|    $1$     |  $7$   |  $7$   |          无          |    $5$     |\n|    $2$     |  $18$  |  $18$  |          无          |    $5$     |\n|    $3$     |  $10$  | $400$  |          无          |    $10$    |\n|    $4$     | $100$  | $400$  |          无          |    $25$    |\n|    $5$     | $400$  | $400$  | $n=m$ 且最大流为 $n$ |    $10$    |\n|    $6$     | $400$  | $400$  |     最大流为 $n$     |    $25$    |\n|    $7$     | $400$  | $400$  |          无          |    $20$    |"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}