A magical matrix I_x is obtained by right shifting an Identity matrix of size q exactly n times in a circular manner.

q in the above example is 3.

Bob is very fond of such matrices so he embeds them in his m x n matrix where each cell represents the value x of I_x that he embeds. Now he is wondering if he can find a loop connecting 1's across this new matrix such that: Exactly 6 1s are connected and every time a 1 is selected it must be from the same column or row (in an alternate manner). Initially, we can choose any element having 1 and next can choose any element within same row or column. Next element must be from the same column if previously it was from the same row hence every successive selection must be in an alternate manner.

Two such paths are shown in the above image (q is taken 3). A path is considered unique if it has at least one node different in it.

Input

The first line of each input test case contains 3 integers m (1 < m ≤ 12), n (1 < n ≤ 6) and q (1 < q ≤ 100)

Next lines contain the matrix having m rows and n columns

Output

Print an integer which tells the number of such paths possible

Example

Input:
3 3 3
1 2 3
4 5 6
7 8 9

Output:
18