Problem Description

Given $n, m, k$, two positive integer sequences $a_{1...n}, b_{1...m}$, and a $k \times k$ $01$ matrix $s_{1...k,1...k}$.

Consider a directed graph $G=(V,E)$, where $V=\{S,T\}\cup(\{0,1\}\times ([1,k]\cap\mathbb{Z})^2)$, and $E=E_1\cup E_2\cup E_3$ consists of three parts:

• $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\}$

Simply put, you can think of each cell $(i,j)$, $1\le i,j\le k$, as being split into an in-node $(0,i,j)$ and an out-node $(1,i,j)$. $E_1$ describes the edges between $S, T$ and these nodes, determined by $a, b$. $E_2$ describes edges from the out-node of each cell to the in-node of the cell above it and the cell to its right. $E_3$ describes edges from the in-node to the out-node within each cell, determined by $s$.

Now treat $G$ as a flow network where every edge has capacity $1$. You need to find the maximum flow from source $S$ to sink $T$, and the number of maximum flows (two flows are considered different if and only if there exists an edge whose flow value differs between the two flows).

Input Format

The first line contains three positive integers $n, m, k$.

The second line contains $n$ positive integers $1\le a_1<a_2<...<a_n\le k$.

The third line contains $m$ positive integers $1\le b_1<b_2<...<b_m\le k$.

Then follow $k$ lines, each a binary string of length $k$, representing the matrix $s$.

Output Format

Output one line with two non-negative integers, representing the maximum flow and the number of maximum flows, respectively. The latter should be taken modulo $10^9+7$.

Hint

The sample is provided in the attached file.

For all testdata, $1\le n,m\le k\le400$.

Translated by ChatGPT 5