You are given a matrix A having N rows and M columns. The rows are numbered from 1 to N from top to bottom and columns are numbered from 1 to M from left to right. You are allowed to move right and down only, that is if you are at cell (i, j), then you can move to (i+1, j) and (i, j+1). You are not allowed to move outside the matrix.

Your task is to find the number of good path starting from (1,1) to (N,M).

Good Path: If the sum of all the elements that lie in the path is divisble by K, then the path is considered as good.

Constraints

1 <= N, M <= 16

1 <= Ai, K <= 10^18

Sample Input

3

3

23

1 2 3

4 5 6

7 8 9

Sample Output

1

Explanation

N = 3, M = 3, K = 23

1->2->5->6->9, Sum is 23 which is divisble by 23 and there is only one good path in the above sample matrix, So the output is 1.