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 divisible by 23 and there is only one good path in the above sample matrix, So the output is 1.

I did brute force, and was able to pass some test cases, but I have no idea how to solve it optimally. If anybody can help, it will be appreciated.