Given $n, m, k$, two sequences of positive integers $a_{1...n}, b_{1...m}$, and a $k \times k$ binary 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)) \mid 1 \le i < k, 1 \le j \le k\} \cup \{((1, i, j), (0, i, j+1)) \mid 1 \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)$ for $1 \le i, j \le k$ as being split into an input node $(0, i, j)$ and an output node $(1, i, j)$. $E_1$ describes the edges between $S, T$ and these nodes, determined by $a$ and $b$; $E_2$ describes the edges from the output node of each cell to the input nodes of the cells directly below and to the right; $E_3$ describes the edges from the input node to the output node of each cell, determined by $s$.

Now, consider $G$ as a network where each edge has a capacity of $1$. You need to find the maximum flow from source $S$ to sink $T$, and the number of such maximum flows (two flows are considered different if and only if there exists an edge that carries a different amount of flow in the two flows).

Input

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

The next $k$ lines each contain a binary string of length $k$, representing the matrix $s$.

Output

Output a single line containing two non-negative integers: the maximum flow and the number of maximum flows, the latter modulo $10^9+7$.

Constraints

For all data, $1 \le n, m \le k \le 400$.