Given a set of m distinct positive integers and a value ‘N’. Count the total number of ways we can form ‘N’ by  adding the array elements. Repetitions and different arrangements are allowed.
Note: Answer can be quite large output the answer modulo 10^{9}+7.
Example 1:
Input:
m = 3 , N = 7
Arr[] = {1,5,6}
Output: 6
Explanation: The different ways are:
1+1+1+1+1+1+1
1+1+5
1+5+1
5+1+1
1+6
6+1
Ã¢â¬â¹Example 2:
Input: 
m = 3 , N = 3
Arr[] = {1,2,3}
Output: 4
Explanation: The different ways are:
1+1+1
1+2
2+1
3  
Your Task:
You don't need to read input or print anything. Your task is to complete the function countWays() which accepts array arr[], its size m and integer N and returns the total number of ways we can form ‘N’ by adding array elements.
Expected Time Complexity: O(N*m)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N , m <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def countWays(self, arr, m, n):
        # code here 

Solutions:
class Solution:

	def countWays(self, nums, m, target):
		n = len(nums)
		nums.sort()
		dp = [0 for _ in range(target + 1)]
		dp[0] = 1
		for total in range(1, target + 1):
			for i in range(n):
				if total - nums[i] >= 0:
					dp[total] += dp[total - nums[i]]
		return dp[target] % (10 ** 9 + 7)


class Solution:

	def countWays(self, arr, m, n):
		mod = int(1000000000.0 + 7)
		dp = [0] * (n + 1)
		dp[0] = 1
		for i in range(1, n + 1):
			for j in arr:
				if j <= i:
					dp[i] += dp[i - j]
			dp[i] = dp[i] % mod
		return dp[n]


class Solution:

	def countWays(self, arr, m, n):
		dp = [0] * (n + 1)
		dp[0] = 1
		mod = 10 ** 9 + 7
		for i in range(1, n + 1):
			for j in range(m):
				if i - arr[j] >= 0:
					dp[i] = (dp[i] + dp[i - arr[j]]) % mod
		return dp[n]


class Solution:

	def __init__(self):
		self.a1 = {}

	def dp(self, a, s):
		if s == 0:
			self.a1[s] = 1
			return
		elif s in self.a1:
			return
		else:
			g = 0
			for i in a:
				if s - i >= 0:
					self.dp(a, s - i)
					g += self.a1[s - i]
			self.a1[s] = g

	def countWays(self, arr, m, n):
		self.dp(arr, n)
		return self.a1[n] % 1000000007


class Solution:

	def __init__(self):
		self.dp = dict()

	def countWays(self, arr, m, n):
		if not n:
			return 1
		if self.dp.get(n) != None:
			return self.dp[n]
		way = 0
		for x in arr:
			if x > n:
				continue
			way += self.countWays(arr, m, n - x)
		self.dp[n] = way % (10 ** 9 + 7)
		return self.dp[n]


class Solution:

	def countWays(self, arr, m, n):
		if not arr:
			return
		Mod = 1000000007
		if n < min(arr):
			return 0
		dp = [1] + [0] * n
		for i in range(1, n + 1):
			for j in range(m):
				if arr[j] <= i:
					dp[i] = dp[i] + dp[i - arr[j]] % Mod
					dp[i] %= Mod
		return dp[n]


class Solution:

	def countWays(self, arr, m, n):
		dp = [0] * (n + 1)
		dp[0] = 1
		mod = 1000000007
		for i in range(1, n + 1):
			for j in arr:
				if i - j >= 0:
					dp[i] = dp[i] % mod + dp[i - j] % mod
		return dp[n] % mod


class Solution:

	def countWays(self, arr, m, n):
		x = max(arr)
		x = max(x, n)
		dp = [0] * (x + 1)
		for el in arr:
			dp[el] += 1
		for i in range(n + 1):
			for el in arr:
				if i - el > 0:
					dp[i] += dp[i - el]
		return dp[n] % 1000000007


MOD = int(1000000000.0 + 7)

def f(A, summ, dp):
	if summ == 0:
		return 1
	if dp[summ] != -1:
		return dp[summ]
	ans = 0
	for i in A:
		if i <= summ:
			ans += f(A, summ - i, dp)
			ans %= MOD
	dp[summ] = ans
	return ans

class Solution:

	def countWays(self, A, m, n):
		dp = [-1 for i in range(n + 1)]
		ans = 0
		for i in A:
			if i <= n:
				ans += f(A, n - i, dp)
				ans %= MOD
		return ans


def wayPresentUsingDP(arr, total, tar, dp):
	if total == tar:
		return 1
	if total > tar:
		return 0
	if dp[total] != -4:
		return dp[total]
	ans = 0
	for (i, data) in enumerate(arr):
		if total + data <= tar:
			ans += wayPresentUsingDP(arr, total + data, tar, dp)
	dp[total] = ans
	return ans

class Solution:

	def countWays(self, arr, m, n):
		dp = [-4] * (n + 1)
		arr = sorted(arr)
		ans = wayPresentUsingDP(arr, 0, n, dp) % (10 ** 9 + 7)
		return ans


class Solution:

	def countWays(self, arr, m, n):
		p = 10 ** 9 + 7
		count = [0 for i in range(n + 1)]
		count[0] = 1
		for i in range(1, n + 1):
			for j in range(m):
				if i >= arr[j]:
					count[i] += count[i - arr[j]]
		return count[n] % p


class Solution:

	def countWays(self, arr, m, n):
		sum = n
		N = m
		coins = arr
		d = [0] * (sum + 1)
		d[0] = 1
		for i in range(sum + 1):
			for j in range(N):
				if coins[j] + i <= sum:
					d[coins[j] + i] = d[i] + d[i + coins[j]]
		return d[-1] % 1000000007


class Solution:

	def countWays(self, arr, m, n):
		dp = {}
		dp[0] = 1
		for i in range(1, n + 1):
			for j in range(m):
				if i >= arr[j]:
					if i not in dp:
						if i - arr[j] not in dp:
							dp[i] = 0
						else:
							dp[i] = dp[i - arr[j]] % (10 ** 9 + 7)
					elif i - arr[j] not in dp:
						dp[i] = dp[i] % (10 ** 9 + 7)
					else:
						dp[i] = (dp[i] + dp[i - arr[j]]) % (10 ** 9 + 7)
		if n in dp:
			return dp[n]
		else:
			return 0


class Solution:

	def countWays(self, arr, m, n):
		dp = [0] * (n + 1)
		ans = self.solve1(arr, n, dp)
		return ans

	def solve(self, num, summ, dp):
		if summ == 0:
			return 1
		if summ < 0:
			return 0
		if dp[summ] != -1:
			return dp[summ]
		a = 0
		for i in range(len(num)):
			a += self.solve(num, summ - num[i], dp)
		dp[summ] = a
		return dp[summ]

	def solve1(self, num, summ, dp):
		if summ == 0:
			return 1
		if summ < 0:
			return 0
		dp[0] = 1
		for i in range(1, n + 1):
			for j in range(len(num)):
				if i - num[j] >= 0:
					dp[i] += dp[i - num[j]]
		return dp[summ] % 1000000007


class Solution:

	def countWays(self, arr, m, n):

		def recursive(ind, arr, cur_sum, n):
			if cur_sum > n:
				return 0
			if cur_sum == n:
				return 1
			if ind == len(arr):
				return 0
			temp = 0
			for i in range(len(arr)):
				temp += recursive(i, arr, cur_sum + arr[i], n) % (10 ** 9 + 7)
			return temp

		def memoized(ind, arr, cur_sum, n, dp):
			if (ind, cur_sum) in dp:
				return dp[ind, cur_sum]
			if cur_sum > n:
				return 0
			if cur_sum == n:
				dp[ind, cur_sum] = 1
				return 1
			if ind == len(arr):
				return 0
			dp[ind, cur_sum] = 0
			for i in range(len(arr)):
				dp[ind, cur_sum] += memoized(i, arr, cur_sum + arr[i], n, dp) % (10 ** 9 + 7)
			return dp[ind, cur_sum]

		def tabulation(arr, n, m):
			dp = [0] * (n + 1)
			dp[-1] = 1
			for j in range(n, -1, -1):
				for k in range(m):
					if j + arr[k] <= n:
						dp[j] = (dp[j] + dp[j + arr[k]]) % (10 ** 9 + 7)
			return dp[0] % (10 ** 9 + 7)
		return tabulation(arr, n, m)
		return memoized(0, arr, 0, n, {})
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(m, n) = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.countWays(arr, m, n))


class Solution:

	def countWays(self, arr, n, total):
		temp = 10 ** 9 + 7
		dp = [0 for i in range(total + 1)]
		dp[0] = 1
		for i in range(1, total + 1):
			for j in range(n):
				if arr[j] <= i:
					dp[i] += dp[i - arr[j]]
					dp[i] %= temp
		return dp[total]


class Solution:

	def countWays(self, arr, m, N):
		mod = 10 ** 9 + 7
		count = [0 for i in range(N + 1)]
		count[0] = 1
		for i in range(1, N + 1):
			for j in range(m):
				if i >= arr[j]:
					count[i] += count[i - arr[j]]
		return count[N] % mod


class Solution:

	def countWays(self, nums, m, target):
		dp = [0] * (target + 1)
		for i in range(1, target + 1):
			for n in nums:
				if n == i:
					dp[i] += 1
				if n < i:
					dp[i] += dp[i - n]
		return dp[-1] % (10 ** 9 + 7)


class Solution:

	def countWays(self, arr, m, n):
		dp = [0] * (n + 1)
		dp[0] = 1
		arr.sort()
		for i in range(1, n + 1):
			for no in arr:
				if no > i:
					continue
				dp[i] = dp[i] + dp[i - no]
		return dp[n] % 1000000007


class Solution:

	def countWays(self, arr, m, N):
		dp = [0 for _ in range(N + 1)]
		MOD = 10 ** 9 + 7
		dp[0] = 1
		for i in range(1, N + 1):
			for num in arr:
				if i - num >= 0:
					dp[i] = int((dp[i - num] + dp[i]) % MOD)
		return dp[N]


class Solution:

	def countWays(self, arr, m, n):
		ways = [1] + n * [0]
		for i in range(n + 1):
			for num in arr:
				if num + i > n:
					continue
				ways[num + i] += ways[i]
				ways[num + i] %= 1000000007
		return ways[-1]


class Solution:

	def countWays(self, arr, m, N):
		dp = [0] * (N + 1)
		dp[0] = 1
		s = 0
		for i in range(1, N + 1):
			for j in range(m):
				if arr[j] <= i:
					s += dp[i - arr[j]]
			dp[i] = s
			s = 0
		return dp[N] % (10 ** 9 + 7)


class Solution:

	def countWays(self, arr, size, target):
		dp = [0] * (target + 1)
		dp[0] = 1
		mod = 1000000007
		for i in range(1, target + 1):
			for coin in arr:
				if coin <= i:
					dp[i] = (dp[i] + dp[i - coin]) % mod
		return dp[target]


class Solution:

	def dfs(self, arr, s, d):
		if s == 0:
			return 1
		if d.get(s) != None:
			return d[s]
		y = 0
		for i in arr:
			if s - i >= 0:
				y = y + self.dfs(arr, s - i, d)
		d[s] = y
		return y

	def countWays(self, arr, m, n):
		d = dict()
		mod = 10 ** 9 + 7
		return self.dfs(arr, n, d) % mod


class Solution:

	def countWays(self, arr, n, s):
		count = [0 for i in range(s + 1)]
		count[0] = 1
		for j in range(1, s + 1):
			for e in arr:
				if j >= e:
					count[j] += count[j - e]
		return count[s] % (pow(10, 9) + 7)