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.

Hi. I recently came accross this question. Link

Given a 2d array where 1 represent a stone and 0 represent water. Return how many path exist in the matrix from top row to the bottom row. You can travel in all directions (top, bottom, left, right) by one position.

Input: [[0, 1, 0, 1, 1],

[0, 1, 1, 0, 1],

[0, 0, 1, 1, 0],

[0, 0, 0, 1, 1]]

The first obvious thought that comes to my mind is backtracking, but that will have large time complexity. How to do this optimally?