Given a N x N matrix such that each of its cells contains some coins. Count the number of ways to collect exactly K coins while moving from top left corner of the matrix to the bottom right. From a cell (i, j), you can only move to (i+1, j) or (i, j+1).
Example 1:
Input:
K = 12, N = 3
arr[] = [[1, 2, 3], 
         [4, 6, 5], 
         [3, 2, 1]]
Output: 2
Explanation: 
There are 2 possible paths 
with exactly K coins, (1 + 2 + 
6 + 2 + 1) and (1 + 2 + 3 + 5 + 1).
Example 2:
Input:
K = 16, N = 3
arr[] = [[1, 2, 3], 
         [4, 6, 5], 
         [9, 8, 7]]
Output: 0 
Explanation: 
There are no possible paths that lead 
to sum=16
Your Task:  
You don't need to read input or print anything. Your task is to complete the function numberOfPath() which takes N, K and 2D matrix arr[][] as input parameters and returns the number of possible paths.
Expected Time Complexity: O(n*n*k)
Expected Auxiliary Space: O(n*n*k)
Constraints:
1 <= K < 100
1 <= N < 100
1 <= arr_{ij} <= 200

Difficulty: MEDIUM
Tags: Matrices

Dynamic programming

Data structures

Complete search
Skill types: Dynamic programming

Data structures

Complete search
Expected Time Complexity: O(n*n*k)
Expected Auxiliary Space: O(n*n*k)

Starter code:
#User function Template for python3



class Solution:

    def numberOfPath (self, N, K, arr):

        # code here





Solutions:
class Solution:

	def util(self, a, i, j, n, m, k):
		global dp
		if i >= n or j >= m or k < 0:
			return 0
		if i == n - 1 and j == m - 1:
			if k - a[i][j] == 0:
				return 1
			return 0
		if dp[i][j][k] != -1:
			return dp[i][j][k]
		dp[i][j][k] = self.util(a, i + 1, j, n, m, k - a[i][j]) + self.util(a, i, j + 1, n, m, k - a[i][j])
		return dp[i][j][k]

	def numberOfPath(self, N, K, arr):
		global dp
		dp = [[[-1 for x in range(K + 1)] for i in range(N)] for j in range(N)]
		return self.util(arr, 0, 0, N, N, K)


from collections import defaultdict as dd

class Solution:

	def numberOfPath(self, N, K, arr):
		store = []
		for i in range(N):
			store.append([])
			for j in range(N):
				store[-1].append({})
		store[0][0][arr[0][0]] = 1
		for i in range(1, N):
			store[0][i][list(store[0][i - 1].keys())[0] + arr[0][i]] = 1
			store[i][0][list(store[i - 1][0].keys())[0] + arr[i][0]] = 1
		for i in range(1, N):
			for j in range(1, N):
				for item in store[i - 1][j].keys():
					store[i][j][item + arr[i][j]] = store[i - 1][j][item]
				for item in store[i][j - 1].keys():
					if item + arr[i][j] in store[i][j]:
						store[i][j][item + arr[i][j]] += store[i][j - 1][item]
					else:
						store[i][j][item + arr[i][j]] = store[i][j - 1][item]
		return store[N - 1][N - 1][K] if K in store[N - 1][N - 1] else 0


class Solution:

	def numberOfPath(self, N, K, arr):

		def solve(i, j, n, k, arr, dp):
			if i >= n or j >= n or k < 0:
				return 0
			if i == n - 1 and j == n - 1:
				if k == arr[i][j]:
					return 1
				return 0
			if (i, j, k) in ways:
				return ways[i, j, k]
			ways[i, j, k] = solve(i + 1, j, n, k - arr[i][j], arr, dp) + solve(i, j + 1, n, k - arr[i][j], arr, dp)
			return ways[i, j, k]
		ways = {}
		return solve(0, 0, N, K, arr, ways)


class Solution:

	def numberOfPath(self, N, K, arr):
		memo = {}

		def helper(i, j, k):
			if i >= N or j >= N or k < 0:
				return 0
			if i == N - 1 and j == N - 1:
				return 1 if k == arr[i][j] else 0
			if (i, j, k) in memo:
				return memo[i, j, k]
			ways = helper(i + 1, j, k - arr[i][j]) + helper(i, j + 1, k - arr[i][j])
			memo[i, j, k] = ways
			return ways
		return helper(0, 0, K)


class Solution:

	def numberOfPath(self, N, K, A):

		def _solve(r, c, left):
			if r >= N or c >= N:
				return 0
			cell = A[r][c]
			if cell > left:
				return 0
			if r == c == N - 1:
				return 1 if left == cell else 0
			v = dp[r][c].get(left, -1)
			if v >= 0:
				return v
			ans = dp[r][c][left] = _solve(r + 1, c, left - cell) + _solve(r, c + 1, left - cell)
			return ans
		dp = [[{} for _ in range(N)] for _ in range(N)]
		ans = _solve(0, 0, K)
		return ans


class Solution:

	def numberOfPath(self, N, K, arr):
		paths = {}
		for y in range(N - 1, -1, -1):
			for x in range(N - 1, -1, -1):
				coord = (x, y)
				coins = arr[x][y]
				if x < N - 1:
					x_paths = paths.get((x + 1, y), {})
				else:
					x_paths = {}
				if y < N - 1:
					y_paths = paths.get((x, y + 1), {})
				else:
					y_paths = {}
				my_paths = {}
				for (k, path_count) in x_paths.items():
					my_paths[k] = my_paths.get(k, 0) + path_count
				for (k, path_count) in y_paths.items():
					my_paths[k] = my_paths.get(k, 0) + path_count
				new_paths = {}
				if not my_paths and x == N - 1 and (y == N - 1):
					new_paths[coins] = 1
				else:
					for (k, path_count) in my_paths.items():
						new_val = k + coins
						if new_val <= K:
							new_paths[new_val] = path_count
				paths[coord] = new_paths
		return paths[0, 0].get(K, 0)


from collections import defaultdict as dd
from collections import Counter

class Solution:

	def numberOfPath(self, N, K, arr):
		store = []
		for i in range(N):
			store.append([])
			for j in range(N):
				store[-1].append(dd(lambda : 0))
		store[0][0][arr[0][0]] += 1
		for i in range(1, N):
			store[0][i][list(store[0][i - 1].keys())[0] + arr[0][i]] += 1
			store[i][0][list(store[i - 1][0].keys())[0] + arr[i][0]] += 1
		for i in range(1, N):
			for j in range(1, N):
				coins = arr[i][j]
				current_store = store[i][j]
				up_store = store[i - 1][j]
				left_store = store[i][j - 1]
				for item in store[i - 1][j].keys():
					current_store[item + coins] += up_store[item]
				for item in store[i][j - 1].keys():
					current_store[item + coins] += left_store[item]
		return store[N - 1][N - 1][K]


def pathCountDPRecDP(mat, m, n, k, dp):
	if m < 0 or n < 0 or k < 0:
		return 0
	elif m == 0 and n == 0:
		return k == mat[m][n]
	if dp[m][n][k] != -1:
		return dp[m][n][k]
	dp[m][n][k] = pathCountDPRecDP(mat, m - 1, n, k - mat[m][n], dp) + pathCountDPRecDP(mat, m, n - 1, k - mat[m][n], dp)
	return dp[m][n][k]

class Solution:

	def numberOfPath(self, N, K, arr):
		dp = [[[-1 for co in range(K + 1)] for col in range(N + 1)] for row in range(N + 1)]
		return int(pathCountDPRecDP(arr, N - 1, N - 1, K, dp))


class Solution:

	def numberOfPath(self, N, K, arr):

		def func(ind1, ind2, k, arr, dp, n):
			if ind1 >= n or ind2 >= n:
				return 0
			if k < 0:
				return 0
			if ind1 == n - 1 and ind2 == n - 1:
				if k == arr[ind1][ind2]:
					return 1
				return 0
			if dp[ind1][ind2][k] != 0:
				return dp[ind1][ind2][k]
			down = func(ind1 + 1, ind2, k - arr[ind1][ind2], arr, dp, n)
			right = func(ind1, ind2 + 1, k - arr[ind1][ind2], arr, dp, n)
			dp[ind1][ind2][k] = down + right
			return dp[ind1][ind2][k]
		dp = [[[0] * (K + 1) for i in range(N)] for j in range(N)]
		kk = func(0, 0, K, arr, dp, N)
		return kk


class Solution:

	def numberOfPath(self, N, K, arr):
		dp = {}

		def fun(i, j, su):
			if i >= N or j >= N:
				return 0
			if i == N - 1 and j == N - 1:
				if su == arr[i][j]:
					return 1
				else:
					return 0
			if su < 0:
				return 0
			if (i, j, su) in dp:
				return dp[i, j, su]
			dp[i, j, su] = fun(i + 1, j, su - arr[i][j]) + fun(i, j + 1, su - arr[i][j])
			return dp[i, j, su]
		return fun(0, 0, K)


class Solution:

	def numberOfPath(self, N, K, arr):
		t = [[[-1 for _ in range(100 + 1)] for j in range(N + 1)] for k in range(N + 1)]

		def solve(r, c, rem):
			if r < 0 or c < 0 or r >= N or (c >= N) or (rem < 0):
				return 0
			if r == N - 1 and c == N - 1:
				return int(rem == arr[r][c])
			if t[r][c][rem] != -1:
				return t[r][c][rem]
			t[r][c][rem] = solve(r + 1, c, rem - arr[r][c]) + solve(r, c + 1, rem - arr[r][c])
			return t[r][c][rem]
		return solve(0, 0, K)


class Solution:

	def numberOfPath(self, N, K, arr):
		if not arr:
			return
		if N == 1 and K > arr[0][0]:
			return 0
		dp = [[[-1 for col in range(K + 1)] for col in range(N + 1)] for row in range(N + 1)]

		def pathCountDPRecDP(arr, m, n, k):
			if m < 0 or n < 0 or k < 0:
				return 0
			elif m == 0 and n == 0:
				if k == arr[m][n]:
					return 1
				else:
					return 0
			if dp[m][n][k] != -1:
				return dp[m][n][k]
			dp[m][n][k] = pathCountDPRecDP(arr, m - 1, n, k - arr[m][n]) + pathCountDPRecDP(arr, m, n - 1, k - arr[m][n])
			return dp[m][n][k]
		return pathCountDPRecDP(arr, N - 1, N - 1, K)


def helper(i, j, s, arr, n, m, dp):
	if not i and (not j):
		return 1 if s == arr[i][j] else 0
	if i < 0 or j < 0 or s < 1:
		return 0
	if dp[i][j][s] != -1:
		return dp[i][j][s]
	up = helper(i - 1, j, s - arr[i][j], arr, n, m, dp)
	dn = helper(i, j - 1, s - arr[i][j], arr, n, m, dp)
	dp[i][j][s] = up + dn
	return dp[i][j][s]

class Solution:

	def numberOfPath(self, N, K, arr):
		si = len(arr)
		le = len(arr[0])
		assert si == N and le == N
		dp = [[[-1] * (K + 1) for _ in range(N)] for _ in range(N)]
		ans = helper(N - 1, N - 1, K, arr, N, N, dp)
		return ans


class Solution:

	def numberOfPath(self, n, k, a):
		v = [[False] * n for i in range(n)]
		d = [[] * n for i in range(n)]
		dp = {}
		for i in range(n):
			for j in range(n):
				d[i].append(dp.copy())
		d[n - 1][n - 1][a[n - 1][n - 1]] = 1

		def solve(i, j, d, v):
			if i > n - 1 or j > n - 1:
				return {}
			if v[i][j]:
				return d[i][j]
			else:
				x = solve(i, j + 1, d, v)
				y = solve(i + 1, j, d, v)
				for z in x:
					if z + a[i][j] not in d[i][j]:
						d[i][j][z + a[i][j]] = x[z]
					else:
						d[i][j][z + a[i][j]] += x[z]
				for z in y:
					if z + a[i][j] not in d[i][j]:
						d[i][j][z + a[i][j]] = y[z]
					else:
						d[i][j][z + a[i][j]] += y[z]
				v[i][j] = True
				return d[i][j]
		d[0][0] = solve(0, 0, d, v)
		if k in d[0][0]:
			return d[0][0][k]
		return 0


def f(A, N, summ, x, y, dp):
	if x >= N or y >= N or summ < 0:
		return 0
	if x == N - 1 and y == N - 1 and (summ - A[x][y] == 0):
		return 1
	if dp[x][y][summ] != -1:
		return dp[x][y][summ]
	ans = f(A, N, summ - A[x][y], x + 1, y, dp) + f(A, N, summ - A[x][y], x, y + 1, dp)
	dp[x][y][summ] = ans
	return ans

class Solution:

	def numberOfPath(self, N, K, A):
		dp = [[[-1 for i in range(K + 1)] for i in range(N + 1)] for i in range(N + 1)]
		ans = 0
		try:
			ans = f(A, N, K, 0, 0, dp)
		except Exception as e:
			print(e)
		return ans


class Solution:

	def numberOfPath(self, N, k, arr):
		dp = {}

		def path(i, j, s, dp):
			if i < 0 or j < 0 or i >= N or (j >= N):
				return 0
			if i == N - 1 and j == N - 1:
				s += arr[i][j]
				if s == k:
					return 1
				return 0
			if (i, j, s) in dp:
				return dp[i, j, s]
			dp[i, j, s] = path(i + 1, j, s + arr[i][j], dp) + path(i, j + 1, s + arr[i][j], dp)
			return dp[i, j, s]
		return path(0, 0, 0, dp)


class Solution:

	def solve(self, mat, m, n, k, dp):
		if m < 0 or n < 0 or k < 0:
			return 0
		elif m == 0 and n == 0:
			if k == mat[m][n]:
				return 1
			return 0
		if (m, n, k) in dp:
			return dp[m, n, k]
		dp[m, n, k] = self.solve(mat, m - 1, n, k - mat[m][n], dp) + self.solve(mat, m, n - 1, k - mat[m][n], dp)
		return dp[m, n, k]

	def numberOfPath(self, N, K, arr):
		dp = {}
		return self.solve(arr, N - 1, N - 1, K, dp)


from functools import lru_cache

class Solution:

	def numberOfPath(self, N, coins, mat):
		if not mat:
			return 0
		key = coins - mat[N - 1][N - 1]

		@lru_cache(None)
		def dfs(i, j, curr):
			ans = 0
			if curr < 0:
				return 0
			if i == 0 and i == j:
				if curr == mat[0][0]:
					return 1
				return 0
			if i > 0:
				ans += dfs(i - 1, j, curr - mat[i][j])
			if j > 0:
				ans += dfs(i, j - 1, curr - mat[i][j])
			return ans
		ans = dfs(N - 1, N - 1, coins)
		return ans


class Solution:

	def pathCountDPRecDP(self, mat, m, n, k, dp):
		if m < 0 or n < 0 or k < 0:
			return 0
		elif m == 0 and n == 0:
			return 1 if k == mat[m][n] else 0
		if dp[m][n][k] != -1:
			return dp[m][n][k]
		dp[m][n][k] = self.pathCountDPRecDP(mat, m - 1, n, k - mat[m][n], dp) + self.pathCountDPRecDP(mat, m, n - 1, k - mat[m][n], dp)
		return dp[m][n][k]

	def numberOfPath(self, N, K, arr):
		dp = [[[-1 for col in range(110)] for col in range(N)] for row in range(N)]
		return self.pathCountDPRecDP(arr, N - 1, N - 1, K, dp)

	def numberOfPath1(self, N, K, arr):
		dx = [0, 1]
		dy = [1, 0]

		def inside(x, y):
			return x >= 0 and x < N and (y >= 0) and (y < N)
		dp1 = [[[0 for i in range(K + 5)] for j in range(N + 5)] for k in range(N + 5)]
		for i in range(N):
			for j in range(N):
				dp1[i][j][0] = 1
		for s in range(1, K + 1):
			for x in range(N):
				for y in range(N):
					if x == 0 or y == 0:
						if s - arr[x][y] >= 0:
							dp1[x][y][s] = dp1[x][y][s - arr[x][y]]
					elif s - arr[x][y] >= 0:
						dp1[x][y][s] += dp1[x - 1][y][s - arr[x][y]]
						dp1[x][y][s] += dp1[x][y - 1][s - arr[x][y]]
		return sum(dp1[:][:][K])


class Solution:

	def numberOfPath(self, N, K, arr):

		def dfs(arr, i, j, k):
			if i < 0 or j < 0 or k < 0:
				return 0
			if i == 0 and j == 0:
				return k == arr[i][j]
			if dp[i][j][k] != -1:
				return dp[i][j][k]
			dp[i][j][k] = dfs(arr, i - 1, j, k - arr[i][j]) + dfs(arr, i, j - 1, k - arr[i][j])
			return dp[i][j][k]
		r = len(arr)
		c = len(arr[0])
		dp = [[[-1 for i in range(K + 1)] for j in range(c)] for m in range(r)]
		z = dfs(arr, r - 1, c - 1, K)
		if z == False:
			return 0
		else:
			return z


class Solution:

	def numberOfPath(self, N, K, arr):
		dp = [[[-1] * (K + 1) for _ in range(N)] for __ in range(N)]

		def recur(i, j, k, dp):
			if i >= N or j >= N or k < 0:
				return 0
			if i == N - 1 and j == N - 1:
				if k == arr[i][j]:
					return 1
				return 0
			if dp[i][j][k] != -1:
				return dp[i][j][k]
			dp[i][j][k] = recur(i + 1, j, k - arr[i][j], dp) + recur(i, j + 1, k - arr[i][j], dp)
			return dp[i][j][k]
		return recur(0, 0, K, dp)


class Solution:

	def numberOfPath(self, N, K, arr):
		m = len(arr)
		n = len(arr[0])

		def check(i, j, K):
			if i < 0 or j < 0 or K < 1:
				return 0
			if i == 0 and j == 0:
				if K == arr[i][j]:
					return 1
				else:
					return 0
			if dp[i][j][K] != -1:
				return dp[i][j][K]
			first = check(i - 1, j, K - arr[i][j])
			second = check(i, j - 1, K - arr[i][j])
			dp[i][j][K] = first + second
			return dp[i][j][K]
		dp = [[[-1 for i in range(K + 1)] for i in range(n)] for i in range(n)]
		return check(m - 1, n - 1, K)


class Solution:

	def find(self, i, j, K, arr, N, dp):
		if i == N or j == N:
			return 0
		if i == N - 1 and j == N - 1 and (K - arr[i][j] == 0):
			return 1
		if K <= 0:
			return 0
		if dp[i][j][K] != -1:
			return dp[i][j][K]
		dp[i][j][K] = self.find(i + 1, j, K - arr[i][j], arr, N, dp) + self.find(i, j + 1, K - arr[i][j], arr, N, dp)
		return dp[i][j][K]

	def numberOfPath(self, N, K, arr):
		dp = []
		for i in range(N):
			dp1 = []
			for j in range(N):
				dp2 = []
				for k in range(K + 1):
					dp2.append(-1)
				dp1.append(dp2)
			dp.append(dp1)
		return self.find(0, 0, K, arr, N, dp)
if __name__ == '__main__':
	ob = Solution()
	t = int(input())
	for _ in range(t):
		K = int(input())
		N = int(input())
		l = list(map(int, input().split()))
		arr = list()
		c = 0
		for i in range(0, N):
			temp = list()
			for j in range(0, N):
				temp.append(l[c])
				c += 1
			arr.append(temp)
		ans = ob.numberOfPath(N, K, arr)
		print(ans)


class Solution:

	def memo(self, m, n, cost, grid, dp):
		if m == 0 and n == 0:
			return 1 if cost - grid[m][n] == 0 else 0
		if m < 0 or n < 0 or cost < 0:
			return 0
		if dp[m][n][cost] != -1:
			return dp[m][n][cost]
		dp[m][n][cost] = self.memo(m - 1, n, cost - grid[m][n], grid, dp) + self.memo(m, n - 1, cost - grid[m][n], grid, dp)
		return dp[m][n][cost]

	def numberOfPath(self, N, K, arr):
		dp = [[[-1] * (K + 1) for j in range(N)] for i in range(N)]
		return self.memo(N - 1, N - 1, K, arr, dp)


class Solution:

	def numberOfPath(self, n, k, l):
		dp = [[{} for _ in range(n)] for _ in range(n)]
		dp[-1][-1][l[-1][-1]] = 1
		for i in range(n - 2, -1, -1):
			for t in dp[i + 1][-1]:
				x = t + l[i][-1]
				if x <= k:
					if x in dp[i][-1]:
						dp[i][-1][x] += dp[i + 1][-1][t]
					else:
						dp[i][-1][x] = dp[i + 1][-1][t]
			for t in dp[-1][i + 1]:
				x = t + l[-1][i]
				if x <= k:
					if x in dp[-1][i]:
						dp[-1][i][x] += dp[-1][i + 1][t]
					else:
						dp[-1][i][x] = dp[-1][i + 1][t]
		for i in range(n - 2, -1, -1):
			for j in range(n - 2, -1, -1):
				for t in dp[i + 1][j]:
					x = t + l[i][j]
					if x <= k:
						if x in dp[i][j]:
							dp[i][j][x] += dp[i + 1][j][t]
						else:
							dp[i][j][x] = dp[i + 1][j][t]
				for t in dp[i][j + 1]:
					x = t + l[i][j]
					if x <= k:
						if x in dp[i][j]:
							dp[i][j][x] += dp[i][j + 1][t]
						else:
							dp[i][j][x] = dp[i][j + 1][t]
		if k in dp[0][0]:
			return dp[0][0][k]
		return 0


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:
	dp = [[[-1] * 101 for i in range(101)] for i in range(101)]
	a = [[0] * 101 for i in range(101)]

	def go(self, n, m, k):
		if k < 0:
			return 0
		if m < 0 or n < 0:
			return 0
		if n == 0 and m == 0:
			self.dp[n][m][k] = 1 if k == self.a[n][m] else 0
			return self.dp[n][m][k]
		if self.dp[n][m][k] != -1:
			return self.dp[n][m][k]
		left = self.go(n, m - 1, k - self.a[n][m])
		up = self.go(n - 1, m, k - self.a[n][m])
		self.dp[n][m][k] = left + up
		return self.dp[n][m][k]

	def numberOfPath(self, n, k, arr):
		for i in range(n):
			for j in range(n):
				self.a[i][j] = arr[i][j]
		for i in range(n):
			for j in range(n):
				for l in range(k + 1):
					self.dp[i][j][l] = -1
		self.go(n - 1, n - 1, k)
		return self.dp[n - 1][n - 1][k]


class Solution:

	def numberOfPath(self, N, K, arr):
		dp = [[[-1 for _ in range(K + 1)] for _ in range(N)] for _ in range(N)]
		return self.solve(arr, dp, N, K, 0, 0, 0)

	def solve(self, arr, dp, N, K, x, y, k):
		if x >= N or y >= N or x < 0 or (y < 0) or (k + arr[x][y] > K):
			return 0
		if x == N - 1 and y == N - 1 and (k + arr[x][y] == K):
			return 1
		if dp[x][y][k] != -1:
			return dp[x][y][k]
		dp[x][y][k] = self.solve(arr, dp, N, K, x + 1, y, k + arr[x][y]) + self.solve(arr, dp, N, K, x, y + 1, k + arr[x][y])
		return dp[x][y][k]


class Solution:

	def recur(self, m, n, k, a):
		global dp
		if m < 0 or n < 0 or k < 0:
			return 0
		if m == 0 and n == 0:
			return k == a[0][0]
		if dp[m][n][k]:
			return dp[m][n][k]
		dp[m][n][k] = self.recur(m - 1, n, k - a[m][n], a) + self.recur(m, n - 1, k - a[m][n], a)
		return dp[m][n][k]

	def numberOfPath(self, N, K, arr):
		global dp
		dp = [[[0 for i in range(K + 1)] for j in range(N)] for k in range(N)]
		ans = self.recur(N - 1, N - 1, K, arr)
		return ans if ans else 0


class Solution:

	def f(self, cr, cc, n, k, arr, dp):
		if cr == n - 1 and cc == n - 1:
			if k == 0:
				return 1
			return 0
		if k < 0:
			return 0
		state = (cr, cc, k)
		if state in dp:
			return dp[state]
		if cc + 1 < n:
			a1 = self.f(cr, cc + 1, n, k - arr[cr][cc + 1], arr, dp)
		else:
			a1 = 0
		if cr + 1 < n:
			a2 = self.f(cr + 1, cc, n, k - arr[cr + 1][cc], arr, dp)
		else:
			a2 = 0
		dp[state] = a1 + a2
		return a1 + a2

	def numberOfPath(self, N, K, arr):
		cr = 0
		cc = 0
		n = N
		k = K
		dp = {}
		return self.f(cr, cc, n, k - arr[cr][cc], arr, dp)


class Solution:

	def numberOfPath(self, N, K, arr):
		memo = [[[-1] * (K + 1) for j in range(N)] for i in range(N)]
		return self.dfs(0, 0, N, arr, K, memo)

	def dfs(self, i, j, N, arr, k, memo):
		if i < 0 or i > N - 1 or j < 0 or (j > N - 1):
			return 0
		if memo[i][j][k] != -1:
			return memo[i][j][k]
		if k - arr[i][j] < 0:
			return 0
		if k - arr[i][j] == 0 and i == N - 1 and (j == N - 1):
			return 1
		count = 0
		count += self.dfs(i, j + 1, N, arr, k - arr[i][j], memo)
		count += self.dfs(i + 1, j, N, arr, k - arr[i][j], memo)
		memo[i][j][k] = count
		return count


class Solution:

	def solve(self, i, j, N, K, arr, dp):
		if i < 0 or j < 0 or K < 0:
			return 0
		elif i == 0 and j == 0:
			return int(K == arr[i][j])
		if dp[i][j][K] != -1:
			return dp[i][j][K]
		dp[i][j][K] = self.solve(i - 1, j, N, K - arr[i][j], arr, dp) + self.solve(i, j - 1, N, K - arr[i][j], arr, dp)
		return dp[i][j][K]

	def numberOfPath(self, N, K, arr):
		dp = [[[-1 for k in range(K + 1)] for j in range(N)] for i in range(N)]
		return self.solve(N - 1, N - 1, N, K, arr, dp)


class Solution:

	def numberOfPath(self, N, K, arr):

		def helper(i, j, s, memo):
			if i >= N or j >= N or s <= 0:
				return 0
			if i == N - 1 and j == N - 1 and (s == arr[i][j]):
				return 1
			key = (i, j, s)
			if key in memo:
				return memo[key]
			memo[key] = helper(i + 1, j, s - arr[i][j], memo) + helper(i, j + 1, s - arr[i][j], memo)
			return memo[key]
		memo = {}
		return helper(0, 0, K, memo)


class Solution:

	def numberOfPath(self, N, K, arr):
		d = {}

		def calPathSum(i, j, s):
			if (i, j, s) in d:
				return d[i, j, s]
			if i < 0 or i >= N or j < 0 or (j >= N):
				d[i, j, s] = 0
				return 0
			if i == N - 1 and j == N - 1:
				if s + arr[i][j] == K:
					d[i, j, s] = 1
					return 1
				else:
					d[i, j, s] = 0
					return 0
			else:
				p1 = calPathSum(i + 1, j, arr[i][j] + s)
				p2 = calPathSum(i, j + 1, arr[i][j] + s)
				d[i, j, s] = p1 + p2
				return p1 + p2
		return calPathSum(0, 1, 1) + calPathSum(1, 0, 1)


class Solution:

	def numberOfPath(self, N, K, arr):
		return self.paths(0, 0, K, arr, N, {})

	def paths(self, cr, cc, K, arr, N, memo):
		if cr >= N or cc >= N:
			return 0
		if cr == N - 1 and cc == N - 1:
			if K - arr[cr][cc] != 0:
				return 0
		if cr == N - 1 and cc == N - 1:
			if K - arr[cr][cc] == 0:
				return 1
		currentKey = str(cr) + '-' + str(cc) + '-' + str(K)
		if currentKey in memo:
			return memo[currentKey]
		one = self.paths(cr + 1, cc, K - arr[cr][cc], arr, N, memo)
		two = self.paths(cr, cc + 1, K - arr[cr][cc], arr, N, memo)
		memo[currentKey] = one + two
		return memo[currentKey]


class Solution:

	def numberOfPath(self, N, K, M):
		return dfs(0, 0, M, N, K - M[0][0], {})

def dfs(r, c, M, N, K, memo):
	if (r, c, K) in memo:
		return memo[r, c, K]
	if K < 0:
		return 0
	if (r, c) == (N - 1, N - 1):
		if K == 0:
			return 1
		return 0
	ans = 0
	for (nr, nc) in [(r + 1, c), (r, c + 1)]:
		if nr == N:
			continue
		if nc == N:
			continue
		ans += dfs(nr, nc, M, N, K - M[nr][nc], memo)
	memo[r, c, K] = ans
	return ans


class Solution:

	def numberOfPath(self, N, K, arr):
		memo = {}

		def h(i, j, sum):
			if i >= N or j >= N or sum > K:
				return 0
			if i == N - 1 and j == N - 1:
				return int(sum + arr[i][j] == K)
			if (i, j, sum) in memo:
				return memo[i, j, sum]
			memo[i, j, sum] = h(i + 1, j, arr[i][j] + sum) + h(i, j + 1, arr[i][j] + sum)
			return memo[i, j, sum]
		return h(0, 0, 0)