Description
Domo is a brilliant dog. He needs to find the shape of the key to get out of the room, otherwise, he will not catch up with the FIFA final.
Domo has a key in his hand and wants to modify the shape of this key to match the correct key for this room.
Given the original key and the target key, please find out how many ways Domo can get the target key with exactly K operations.
The key will be a grid that consists of N rows and M columns, which contains exactly one 'x' and others are '1' and '0'.
In each operation, you can swap 'x' with the adjacent element. The element (i, j) is adjacent to the element (i-1, j-1), (i-1, j+1), (i+1, j-1), (i+1, j+1) if it's in the bound.
There're 2 methods for the sample input 1.
Input
The first line consists of three integers N, M, and K. (1 ≤ N, M ≤ 102, 1 ≤ K ≤ 5)
For the next N line, each line consists of M elements, describing the shape of the key in Domo's hand.
For the next N line, each line consists of M elements, describing the correct shape of the key of this room.
Output
Print the number of ways Domo can get the target key with exactly K operations.
Print a newline character at the end of the line.