MAGMAT - Magical Matrices

A magical matrix Ix 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 Ix 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

Added by:Ankit Priyarup
Date:2018-12-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Self Problem

hide comments
2024-01-13 05:22:31 Oleg
Verified with native solution, seems issue with test cases.

Last edit: 2024-01-15 18:51:37
2019-04-24 14:37:49
What is the boundary for values in matrix[m][n]?
2019-01-02 16:43:22 Jacob Plachta
The bounds on the grid dimensions seem to be backwards - the data has m (number of rows) <= 6 and n (number of columns) <= 12, rather than vice versa.

Last edit: 2019-01-02 16:43:33
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.