An arbitration court has been tasked with dividing a piece of a bay claimed by two neighboring countries — country A and country B. The bay can be represented as a rectangular grid consisting of fields organized into $n$ rows, numbered 1 to $n$ from top to bottom, and $m$ columns, numbered 1 to $m$ from left to right. The court employs $n-1$ so-called horizontal judges and $m-1$ so-called vertical judges. Each horizontal judge is responsible for one horizontal line between adjacent rows. Analogously, each vertical judge is responsible for one vertical line between adjacent columns.
Figure 1: A valid combination of votes consistent with the desired division from the first example below.
The result of each judge's work is their vote — a natural number between 1 and $k$, inclusive. The value of a field is an integer calculated by summing the votes of all judges responsible for lines above and to the left of that field, and subtracting the votes of all other judges (those responsible for lines below and to the right). After the voting is finished, the bay is divided such that fields with a negative value belong to country A, and fields with a positive value belong to country B. If the value of any field is zero, the voting result is invalid.
You are given the desired outcome of the division. Specifically, for every field, it is known which country it must belong to. Let $c$ be the number of different combinations of votes such that the voting is valid and results in the given division. Determine the value of $c$ modulo $10^9 + 7$.
Input
The first line contains the natural numbers $n$, $m$, and $k$ — the number of rows and columns of the bay, and the maximum possible vote. Each of the following $n$ lines contains a sequence of $m$ characters describing one row of the bay. Fields that should belong to country A are marked with the character "-", and fields that should belong to country B are marked with "+".
Output
Print the required number of combinations modulo $10^9 + 7$.
Subtasks
In all subtasks, $1 \le m, n, k \le 80$.
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 10 | $n + m \le 10, k \le 4$ |
| 2 | 10 | $m = 1$ |
| 3 | 10 | $n, m, k \le 20$ |
| 4 | 20 | $n, m, k \le 40$ |
| 5 | 20 | $m = n + 1$, the field in the $r$-th row and $s$-th column is marked with "+" if and only if $r + s \ge 1 + m$ |
| 6 | 30 | No additional constraints |
Examples
Input 1
4 6 4 -----+ ----++ --++++ -+++++
Output 1
2364
Input 2
3 3 2 --+ --+ -++
Output 2
2
Input 3
2 3 2 --- +++
Output 3
0