Land Division Assignment

Two countries A and B are dividing a rectangular piece of land of size (n\times m). Clearly there are (n-1) horizontal lines and (m-1) vertical lines inside the rectangle. Each of these (n+m-2) lines is assigned an integer in the interval ([1, k]). For each cell (grid unit) of the land, define its weight as the sum of the integers on the line immediately above and to the left of the cell minus the sum of the integers on the line immediately below and to the right of the cell. In other words, if we denote by (H_i) the integer assigned to the (i)-th horizontal line (for (i=1,\dots,n-1)) and by (V_j) the integer assigned to the (j)-th vertical line (for (j=1,\dots,m-1)), then the weight of the cell in row (i) and column (j) (where (i,j) are 1-indexed) is given by: [ w(i,j) = \begin{cases} ;;H_{i-1} + V_{j-1} - H_i - V_j & \text{if } 1 < i < n \text{ and } 1 < j < m,\ \text{(with appropriate modifications when one of the adjacent lines does not exist)}. \end{cases} ] Each cell comes with a requirement: its weight must be either less than 0 or greater than 0. You are given an (n\times m) grid where each cell contains either the character < (meaning its weight must be less than 0) or > (meaning its weight must be greater than 0). Among the (k^{n+m-2}) possible assignments of integers to the lines, count how many assignments satisfy all the cell requirements. Output the answer modulo (10^9+7).

Note: The input sizes in the test cases are small so that a brute force solution is feasible.

inputFormat

The first line contains three integers (n, m, k). The next (n) lines each contain a string of length (m) consisting only of the characters < and >, which represent the weight requirement for each cell. For a cell with <, its weight must be less than 0; for a cell with >, its weight must be greater than 0.

outputFormat

Output a single integer, the number of valid integer assignments to the lines (modulo (10^9+7)).

sample

2 2 5

10