Given an array arr[] of non-negative integers and an integer sum, the task is to count all subsets of the given array with a sum equal to a given sum.
Note: Answer can be very large, so, output answer modulo 10^{9}+7
Example 1:
Input: N = 6, arr[] = {2, 3, 5, 6, 8, 10}
       sum = 10
Output: 3
Explanation: {2, 3, 5}, {2, 8}, {10}
Example 2:
Input: N = 5, arr[] = {1, 2, 3, 4, 5}
       sum = 10
Output: 3
Explanation: {1, 2, 3, 4}, {1, 4, 5}, 
             {2, 3, 5}
Your Task:  
You don't need to read input or print anything. Complete the function perfectSum() which takes N, array arr[] and sum as input parameters and returns an integer value
Expected Time Complexity: O(N*sum)
Expected Auxiliary Space: O(N*sum)
Constraints:
1 ≤ N*sum ≤ 10^{6}
0<=arr[I]<=10^{6}

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming
Expected Time Complexity: O(N*sum)
Expected Auxiliary Space: O(N*sum)

Starter code:
#User function Template for python3

class Solution:

	def perfectSum(self, arr, n, sum):

		# code here

Solutions:
class Solution:

	def perfectSum(self, arr, n, sum):
		m = 1000000007
		t = [[0 for I in range(sum + 1)] for _ in range(n + 1)]
		t[0][0] = 1
		for i in range(1, n + 1):
			for j in range(sum + 1):
				if arr[i - 1] <= j:
					t[i][j] = (t[i - 1][j - arr[i - 1]] + t[i - 1][j]) % m
				else:
					t[i][j] = t[i - 1][j] % m
		return t[n][sum] % m


class Solution:

	def perfectSum(self, arr, n, sum):
		dp = [[0 for _ in range(sum + 1)] for _ in range(n + 1)]
		dp[0][0] = 1
		for ind in range(1, n + 1):
			for target in range(sum + 1):
				not_take = dp[ind - 1][target]
				take = 0
				if target - arr[ind - 1] >= 0:
					take = dp[ind - 1][target - arr[ind - 1]]
				dp[ind][target] = take + not_take
		return dp[n][sum] % (10 ** 9 + 7)


class Solution:

	def perfectSum(self, arr, n, sum):
		mod = 10 ** 9 + 7

		def recursive(ind, target):
			if ind >= n:
				return target == 0
			if dp[ind][target] != -1:
				return dp[ind][target]
			pick = 0
			if target >= arr[ind]:
				pick = recursive(ind + 1, target - arr[ind])
			nonpick = recursive(ind + 1, target)
			dp[ind][target] = (pick + nonpick) % mod
			return dp[ind][target]
		dp = [[-1 for i in range(sum + 1)] for j in range(n + 1)]
		return recursive(0, sum)


class Solution:

	def perfectSum(self, arr, n, sum):
		dp = [[0 for x in range(sum + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			for j in range(0, sum + 1):
				if arr[i - 1] <= j:
					dp[i][j] = dp[i - 1][j - arr[i - 1]] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n][sum] % 1000000007


class Solution:

	def perfectSum(self, arr, n, sum):
		MOD = 10 ** 9 + 7
		dp = [[0 for _ in range(sum + 1)] for _ in range(n + 1)]
		dp[0][0] = 1
		for i in range(1, n + 1):
			for j in range(sum + 1):
				dp[i][j] = (dp[i - 1][j] + (dp[i - 1][j - arr[i - 1]] if j - arr[i - 1] >= 0 else 0)) % MOD
		return dp[n][sum]


class Solution:

	def dfs(self, i, target, arr, dp):
		if i == -1:
			if target == 0:
				return 1
			return 0
		if dp[i][target] != -1:
			return dp[i][target]
		not_pick = self.dfs(i - 1, target, arr, dp)
		pick = 0
		if arr[i] <= target:
			pick = self.dfs(i - 1, target - arr[i], arr, dp)
		dp[i][target] = not_pick + pick
		return dp[i][target] % 1000000007

	def perfectSum(self, arr, n, sm):
		dp = [[-1 for j in range(sm + 1)] for i in range(n)]
		return self.dfs(n - 1, sm, arr, dp)


class Solution:

	def perfectSum(self, arr, n, sm):
		prev = [0] * (sm + 1)
		prev[0] = 1
		for i in range(1, n + 1):
			cur = [0] * (sm + 1)
			for target in range(0, sm + 1):
				not_pick = prev[target]
				pick = 0
				if arr[i - 1] <= target:
					pick = prev[target - arr[i - 1]]
				cur[target] = not_pick + pick
			prev = cur
		return prev[sm] % 1000000007


class Solution:

	def perfectSum(self, arr, n, sum):
		m = 1000000007
		w = sum + 1
		l = []
		for i in range(n + 1):
			d = []
			for j in range(w):
				d.append(0)
			l.append(d)
		l[0][0] = 1
		for i in range(1, n + 1):
			for j in range(0, sum + 1):
				if arr[i - 1] <= j:
					l[i][j] = (l[i - 1][j - arr[i - 1]] + l[i - 1][j]) % m
				else:
					l[i][j] = l[i - 1][j] % m
		return l[n][sum] % m


class Solution:

	def perfectSum(self, arr, n, sum):
		dp = {}
		arr.sort()
		count = 0

		def helper(ind, target):
			if target < 0:
				return 0
			if ind == n:
				if target == 0:
					return 1
				return 0
			if (ind, target) in dp:
				return dp[ind, target]
			not_take = helper(ind + 1, target)
			take = helper(ind + 1, target - arr[ind])
			dp[ind, target] = take + not_take
			return dp[ind, target]
		return helper(0, sum) % (10 ** 9 + 7)


class Solution:

	def perfectSum(self, arr, n, sum):
		dp = [[0 for _ in range(sum + 1)] for _ in range(n + 1)]
		arr.sort(reverse=True)
		for i in range(n + 1):
			for j in range(sum + 1):
				if j == 0:
					dp[i][j] = 1
		for i in range(1, n + 1):
			for j in range(1, sum + 1):
				if arr[i - 1] <= j:
					dp[i][j] = dp[i - 1][j - arr[i - 1]] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n][sum] % 1000000007


class Solution:

	def perfectSum(self, arr, n, target):
		dp = [0 for _ in range(0, target + 1)]
		dp[0] = 1
		if arr[0] <= target:
			if arr[0] == 0:
				dp[arr[0]] = 2
			else:
				dp[arr[0]] = 1
		for i in range(1, n):
			temp = [0 for _ in range(0, target + 1)]
			for tar in range(target + 1):
				take = 0
				if tar >= arr[i]:
					take = dp[tar - arr[i]]
				noTake = dp[tar]
				temp[tar] = (take + noTake) % (10 ** 9 + 7)
			dp = temp
		return dp[target]

	def rec(self, index, arr, target, dp):
		if index == 0:
			if target == 0 and arr[0] == 0:
				return 2
			if target == 0 or target == arr[index]:
				return 1
			return 0
		if dp[index][target] != -1:
			return dp[index][target]
		take = 0
		if target >= arr[index]:
			take = self.rec(index - 1, arr, target - arr[index], dp)
		notake = self.rec(index - 1, arr, target, dp)
		dp[index][target] = (take + notake) % (10 ** 9 + 7)
		return dp[index][target]


class Solution:

	def perfectSum(self, arr, n, target):
		dp = [[-1 for _ in range(0, target + 1)] for _ in range(n)]
		return self.rec(n - 1, arr, target, dp)

	def rec(self, index, arr, target, dp):
		if index == 0:
			if target == 0 and arr[0] == 0:
				return 2
			if target == 0 or target == arr[index]:
				return 1
			return 0
		if dp[index][target] != -1:
			return dp[index][target]
		take = 0
		if target >= arr[index]:
			take = self.rec(index - 1, arr, target - arr[index], dp)
		notake = self.rec(index - 1, arr, target, dp)
		dp[index][target] = (take + notake) % (10 ** 9 + 7)
		return dp[index][target]


from functools import lru_cache

class Solution:

	def perfectSum(self, arr, n, sum):
		mod = 10 ** 9 + 7
		dp = [0] * (sum + 1)
		dp[0] = 1
		for element in arr:
			for j in range(sum, element - 1, -1):
				dp[j] = (dp[j] + dp[j - element]) % mod
		return dp[sum] % mod


class Solution:

	def perfectSum(self, arr, n, sum):
		arr.sort()
		dp = [[0] * (sum + 1) for _ in range(n + 1)]
		dp[0][0] = 1
		for r in range(1, n + 1):
			for c in range(sum + 1):
				if arr[r - 1] <= c:
					dp[r][c] = dp[r - 1][c - arr[r - 1]] + dp[r - 1][c]
				else:
					dp[r][c] = dp[r - 1][c]
		return dp[-1][-1] % (10 ** 9 + 7)


class Solution:

	def perfectSum(self, arr, n, sum):
		import sys
		sys.setrecursionlimit(10 ** 9 + 7)
		dp = [[-1 for j in range(sum + 1)] for i in range(n)]
		return self.solve(n - 1, sum, arr, dp)

	def solve(self, i, j, arr, dp):
		if i == 0:
			if j == 0 and arr[i] == 0:
				return 2
			if j == 0 or arr[i] == j:
				return 1
			else:
				return 0
		if dp[i][j] != -1:
			return dp[i][j]
		npick = self.solve(i - 1, j, arr, dp)
		pick = 0
		if arr[i] <= j:
			pick = self.solve(i - 1, j - arr[i], arr, dp)
		dp[i][j] = (pick + npick) % (10 ** 9 + 7)
		return dp[i][j]


mod = 1000000000.0 + 7

class Solution:

	def perfectSum(self, arr, n, sum):
		dp = [[0 for i in range(sum + 1)] for j in range(n)]
		for i in range(n):
			dp[i][0] = 1
		if arr[0] <= sum:
			dp[0][arr[0]] = 1
		if arr[0] == 0:
			dp[0][0] = 2
		for ind in range(1, n):
			for tg in range(sum + 1):
				nt = dp[ind - 1][tg]
				t = 0
				if arr[ind] <= tg:
					t = dp[ind - 1][tg - arr[ind]]
				dp[ind][tg] = (nt + t) % mod
		return int(dp[n - 1][sum])


mod = 10 ** 9 + 7

class Solution:

	def perfectSum(self, arr, n, sumi):
		dp = [[0 for i in range(sum + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			for j in range(sum + 1):
				if arr[i - 1] <= j:
					dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i - 1]]
				else:
					dp[i][j] = dp[i - 1][j]
				dp[i][j] %= mod
		return dp[-1][-1] % mod


class Solution:

	def perfectSum(self, arr, n, sum):
		c = [0]
		dp = [[0 for _ in range(sum + 1)] for _ in range(n)]
		mod = 10 ** 9 + 7
		for i in range(n):
			dp[i][0] = 1
		if arr[0] <= sum:
			dp[0][arr[0]] += 1
		for idx in range(1, n):
			for target in range(0, sum + 1):
				pick = 0
				if arr[idx] <= target:
					pick = dp[idx - 1][target - arr[idx]]
				notpick = dp[idx - 1][target]
				dp[idx][target] = pick + notpick
		return dp[-1][-1] % mod

	def findSums(self, arr, idx, sum, dp):
		if idx < 0:
			return sum == 0
		if dp[idx][sum] != 0:
			return dp[idx][sum]
		pick = 0
		if arr[idx] <= sum:
			pick = self.findSums(arr, idx - 1, sum - arr[idx], dp)
		notpick = self.findSums(arr, idx - 1, sum, dp)
		dp[idx][sum] = pick + notpick
		return dp[idx][sum]


from collections import defaultdict

class Solution:

	def perfectSum(self, arr, n, k):
		mod = 10 ** 9 + 7
		dp = [[-1 for i in range(k + 1)] for j in range(n + 1)]

		def sum(i, arr, t, dp):
			if i == 0:
				if t == 0 and arr[0] == 0:
					return 2
				if t == 0 or arr[0] == t:
					return 1
				return 0
			if dp[i][t] != -1:
				return dp[i][t]
			x = sum(i - 1, arr, t, dp)
			y = 0
			if arr[i] <= t:
				y = sum(i - 1, arr, t - arr[i], dp)
			dp[i][t] = (x + y) % mod
			return dp[i][t]
		return sum(len(arr) - 1, arr, k, dp)


from collections import defaultdict

class Solution:

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


class Solution:

	def perfectSum(self, arr, n, sum):
		dp = [[-1 for i in range(sum + 1)] for j in range(n)]

		def countSubsets(i, sum):
			if i == 0:
				if sum == 0 and arr[0] == 0:
					return 2
				if sum == 0 or arr[0] == sum:
					return 1
				return 0
			if dp[i][sum] != -1:
				return dp[i][sum]
			notpick = countSubsets(i - 1, sum)
			pick = countSubsets(i - 1, sum - arr[i]) if sum >= arr[i] else 0
			dp[i][sum] = pick + notpick
			return dp[i][sum] % 1000000007
		return countSubsets(n - 1, sum)


class Solution:

	def perfectSum(self, arr, n, tsm):
		prev = [0] * (tsm + 1)
		prev[0] = 1
		for i in range(1, n + 1):
			cur = [0] * (tsm + 1)
			for sm in range(tsm + 1):
				ln = prev[sm]
				if sm >= arr[i - 1]:
					ln += prev[sm - arr[i - 1]]
				cur[sm] = ln
			prev = cur
		return prev[sm] % 1000000007


mod = 10 ** 9 + 7

class Solution:

	def perfectSum(self, arr, n, sum):
		dp = [[-1 for i in range(sum + 1)] for j in range(n + 1)]

		def memo(idx, target):
			if idx == 0:
				if target == 0:
					if arr[0] == 0:
						return 2
					return 1
				if arr[idx] == target:
					return 1
				return 0
			if dp[idx][target] != -1:
				return dp[idx][target]
			if arr[idx] <= target:
				dp[idx][target] = (memo(idx - 1, target - arr[idx]) + memo(idx - 1, target)) % mod
			else:
				dp[idx][target] = memo(idx - 1, target) % mod
			return dp[idx][target] % mod
		return memo(n - 1, sum)


mod = 10 ** 9 + 7
from collections import deque

class Solution:

	def perfectSum(self, pat, n, sum):
		dp = [[0 for i in range(sum + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			for j in range(sum + 1):
				if arr[i - 1] <= j:
					dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i - 1]]
				else:
					dp[i][j] = dp[i - 1][j]
				dp[i][j] %= mod
		return dp[-1][-1] % mod


class Solution:

	def perfectSum(self, arr, n, key):
		c = 0
		for ele in arr:
			if ele == 0:
				c += 1
		dp = [[0] * (key + 1) for i in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			for j in range(1, key + 1):
				if arr[i - 1] > j or arr[i - 1] == 0:
					dp[i][j] = dp[i - 1][j]
				elif arr[i - 1] <= j:
					dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - arr[i - 1]]) % (pow(10, 9) + 7)
		return pow(2, c) * dp[n][key]


class Solution:

	def perfectSum(self, arr, n, sum):
		mod = 1000000000.0 + 7

		def subs(ind, target):
			if ind == 0:
				if target == 0 and arr[0] == 0:
					dp[ind][target] = 2
					return 2
				if target == 0 or target == arr[0]:
					dp[ind][target] = 1
					return 1
				else:
					dp[ind][target] = 0
					return 0
			if dp[ind][target] != -1:
				return dp[ind][target]
			notTake = subs(ind - 1, target)
			Take = 0
			if target >= arr[ind]:
				Take = subs(ind - 1, target - arr[ind])
			dp[ind][target] = int((Take + notTake) % mod)
			return dp[ind][target]
		dp = [[-1 for i in range(sum + 1)] for i in range(n)]
		subs(n - 1, sum)
		return dp[n - 1][sum]


class Solution:

	def perfectSum(self, arr, n, sum):
		mod = 1000000007
		dp = [1 if i == 0 else 0 for i in range(sum + 1)]
		for i in range(n):
			curr = [0 for k in range(sum + 1)]
			for j in range(sum + 1):
				if i == 0:
					if j == 0 and arr[0] == 0:
						curr[j] = 2
					elif j == 0 or j == arr[0]:
						curr[j] = 1
					if j == 0:
						continue
				not_selected = dp[j]
				selected = 0
				if j >= arr[i]:
					selected = dp[j - arr[i]]
				curr[j] = selected + not_selected
			dp = curr
		return dp[sum] % mod


class Solution:

	def perfectSum(self, arr, n, sum):
		dp = [[-1 for j in range(sum + 1)] for i in range(n)]
		return self.f(n - 1, arr, sum, dp) % 1000000007

	def f(self, index, arr, sum, dp):
		if index == 0:
			if sum == 0 and arr[0] == 0:
				return 2
			elif arr[0] == sum or sum == 0:
				return 1
			return 0
		if dp[index][sum] != -1:
			return dp[index][sum]
		not_take = self.f(index - 1, arr, sum, dp) % 1000000007
		take = 0
		if arr[index] <= sum:
			take = self.f(index - 1, arr, sum - arr[index], dp) % 1000000007
		dp[index][sum] = (take + not_take) % 1000000007
		return dp[index][sum]


class Solution:

	def perfectSum(self, arr, n, tsm):
		dp = [[0 for j in range(tsm + 1)] for i in range(n + 1)]
		dp[0][0] = 1
		for i in range(1, n + 1):
			for sm in range(tsm + 1):
				ln = dp[i - 1][sm]
				if sm >= arr[i - 1]:
					ln += dp[i - 1][sm - arr[i - 1]]
				dp[i][sm] = ln
		return dp[n][sm] % 1000000007


class Solution:

	def perfectSum(self, arr, n, sum):
		a = []
		mod = 10 ** 9 + 7
		for i in range(0, len(arr) + 1):
			li = []
			for j in range(0, sum + 1):
				li.append(0)
			a.append(li)
		for i in range(0, len(arr) + 1):
			for j in range(0, sum + 1):
				if j == 0:
					a[i][j] = 1
		for i in range(1, len(arr) + 1):
			for j in range(0, sum + 1):
				if arr[i - 1] <= j:
					a[i][j] = a[i - 1][j - arr[i - 1]] % mod + a[i - 1][j] % mod
				else:
					a[i][j] = a[i - 1][j] % mod
		return a[n][sum] % mod


class Solution:

	def perfectSum(self, arr, n, sm):
		mo = 1000000007
		dp = [[1 for i in range(sm + 1)] for j in range(n + 1)]
		for i in range(1, sm + 1):
			dp[0][i] = 0
		for i in range(1, n + 1):
			for j in range(sm + 1):
				if arr[i - 1] <= j:
					dp[i][j] = dp[i - 1][j - arr[i - 1]] % mo + dp[i - 1][j] % mo
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[i][j] % mo


class Solution:

	def perfectSum(self, arr, N, sum):
		dp = [[0] * (sum + 1) for _ in range(N)]
		mod = 10 ** 9 + 7
		for i in range(N):
			for j in range(sum + 1):
				item = arr[i]
				sm = j
				if i == 0:
					if sm == 0:
						if item == 0:
							dp[i][j] = 2
						else:
							dp[i][j] = 1
					elif item == sm:
						dp[i][j] = 1
				elif item <= sm:
					dp[i][j] = (dp[i - 1][sm - item] + dp[i - 1][sm]) % mod
				else:
					dp[i][j] = dp[i - 1][sm]
		return dp[N - 1][sm]


class Solution:

	def perfectSum(self, arr, N, sum):
		dp = {}
		mod = 10 ** 9 + 7
		arr.sort(reverse=True)

		def solve(n, sm):
			if n == 0:
				if sm == 0:
					return 1
				else:
					return 0
			elif (n, sm) in dp:
				return dp[n, sm]
			else:
				item = arr[n - 1]
				if item <= sm:
					c1 = solve(n - 1, sm - item)
					c2 = solve(n - 1, sm)
					c = (c1 + c2) % mod
				elif sm == 0:
					c = 1
				else:
					c = 0
				dp[n, sm] = c
				return c
		return solve(N, sum)


class Solution:

	def f(self, ind, target, arr, dp):
		if target == 0:
			return 1
		if ind == 0:
			if arr[ind] == target:
				return 1
			return 0
		if dp[ind][target] != -1:
			return dp[ind][target]
		ntake = self.f(ind - 1, target, arr, dp)
		take = 0
		if arr[ind] <= target:
			take = self.f(ind - 1, target - arr[ind], arr, dp)
		dp[ind][target] = take + ntake
		return dp[ind][target] % (int(1000000000.0) + 7)

	def perfectSum(self, arr, n, sum):
		temp = []
		count = 0
		for i in arr:
			if i == 0:
				count += 1
				continue
			temp.append(i)
		m = n - count
		dp = [[-1 for i in range(sum + 1)] for i in range(m)]
		val = self.f(m - 1, sum, temp, dp)
		return val * (1 << count)


class Solution:

	def f(self, ind, target, arr, dp):
		if ind == 0:
			if target == 0 and arr[0] == 0:
				return 2
			if target == 0 or arr[0] == target:
				return 1
			return 0
		if dp[ind][target] != -1:
			return dp[ind][target]
		ntake = self.f(ind - 1, target, arr, dp)
		take = 0
		if arr[ind] <= target:
			take = self.f(ind - 1, target - arr[ind], arr, dp)
		dp[ind][target] = (take + ntake) % (int(1000000000.0) + 7)
		return dp[ind][target]

	def perfectSum(self, arr, n, sum):
		dp = [[-1 for i in range(sum + 1)] for i in range(n)]
		val = self.f(n - 1, sum, arr, dp)
		return val


class Solution:

	def __init__(self):
		self.MOD = 1000000000 + 7

	def perfectSum(self, arr, n, sum):
		arrays_with_no_zero = []
		no_of_zeros = 0
		for num in arr:
			if num != 0:
				arrays_with_no_zero.append(num)
			else:
				no_of_zeros += 1
		no_of_perfect_subsets = self.space_tab_count_no_of_perfect_subsets(arrays_with_no_zero, sum)
		return self.modulo_multiplication(no_of_perfect_subsets, no_of_zeros)

	def modulo_multiplication(self, no_of_perfect_subsets, no_of_zeros):
		return 2 ** no_of_zeros % self.MOD * (no_of_perfect_subsets % self.MOD) % self.MOD

	def modulo_addition(self, consider_cnt, not_consider_cnt):
		return (consider_cnt % self.MOD + not_consider_cnt % self.MOD) % self.MOD

	def count_no_of_perfect_subsets(self, curr_index, target_sum, last_index, arr, memo):
		if target_sum == 0:
			return 1
		if curr_index == last_index:
			if arr[last_index] == target_sum:
				return 1
			else:
				return 0
		curr_key = (curr_index, target_sum)
		if memo.get(curr_key) != None:
			return memo.get(curr_key)
		curr_val = arr[curr_index]
		consider = 0
		if curr_val <= target_sum:
			consider = self.count_no_of_perfect_subsets(curr_index + 1, target_sum - curr_val, last_index, arr, memo)
		not_consider = self.count_no_of_perfect_subsets(curr_index + 1, target_sum, last_index, arr, memo)
		memo[curr_key] = self.modulo_addition(consider, not_consider)
		return memo.get(curr_key)

	def tab_count_no_of_perfect_subsets(self, arr, target_sum):
		last_index = len(arr) - 1
		memo = [[0 for val in range(target_sum + 1)] for index in range(last_index + 1)]
		for index in range(last_index + 1):
			memo[index][0] = 1
		if arr[last_index] <= target_sum:
			memo[last_index][arr[last_index]] = 1
		for curr_index in range(last_index - 1, -1, -1):
			for curr_sum in range(1, target_sum + 1, 1):
				curr_val = arr[curr_index]
				consider = 0
				if curr_val <= curr_sum:
					consider = memo[curr_index + 1][curr_sum - curr_val]
				not_consider = memo[curr_index + 1][curr_sum]
				memo[curr_index][curr_sum] = self.modulo_addition(consider, not_consider)
		return memo[0][target_sum]

	def space_tab_count_no_of_perfect_subsets(self, arr, target_sum):
		last_index = len(arr) - 1
		prev = None
		for curr_index in range(last_index, -1, -1):
			temp = [0 for val in range(target_sum + 1)]
			for curr_sum in range(0, target_sum + 1, 1):
				if curr_sum == 0:
					temp[curr_sum] = 1
					continue
				if curr_index == last_index:
					if arr[curr_index] == curr_sum:
						temp[curr_sum] = 1
					continue
				curr_val = arr[curr_index]
				consider = 0
				if curr_val <= curr_sum:
					consider = prev[curr_sum - curr_val]
				not_consider = prev[curr_sum]
				temp[curr_sum] = self.modulo_addition(consider, not_consider)
			prev = temp
		return prev[target_sum]


class Solution:

	def perfectSum(self, arr, n, sum):
		mod = int(1000000000.0 + 7)
		t = [[0 for j in range(sum + 1)] for i in range(n + 1)]
		t[0][0] = 1
		for j in range(1, sum + 1):
			t[0][j] = 0
		for i in range(1, n + 1):
			for j in range(sum + 1):
				if arr[i - 1] > j:
					t[i][j] = t[i - 1][j] % mod
				else:
					t[i][j] = (t[i - 1][j - arr[i - 1]] % mod + t[i - 1][j] % mod) % mod
		return t[n][sum] % mod


class Solution:

	def perfectSum(self, arr, n, Sum):
		dp = [['.'] * (Sum + 1) for i in range(n + 1)]
		mod = 10 ** 9 + 7
		for i in range(n + 1):
			for j in range(Sum + 1):
				if i == 0:
					dp[i][j] = 0
				if j == 0:
					if arr[i - 1] == 0 and i > 0:
						dp[i][j] = 2 * dp[i - 1][j]
					else:
						dp[i][j] = 1
		for i in range(1, n + 1):
			for j in range(1, Sum + 1):
				if arr[i - 1] <= j:
					dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i - 1]]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[-1][-1] % mod


m = 10 ** 9 + 7

class Solution:

	def perfectSum(self, arr, n, sum):
		t = [[0 for j in range(sum + 1)] for i in range(n + 1)]
		for j in range(sum + 1):
			t[0][j] = 0
		t[0][0] = 1
		for i in range(1, n + 1):
			for j in range(0, sum + 1):
				if arr[i - 1] <= j:
					t[i][j] = t[i - 1][j - arr[i - 1]] + t[i - 1][j]
				else:
					t[i][j] = t[i - 1][j]
				t[i][j] %= m
		return t[n][sum] % m


class Solution:

	def count_zeros_till_index(self, arr, i):
		count = 0
		for j in range(i):
			if arr[j] == 0:
				count += 1
		return count

	def perfectSum(self, arr, n, sum):
		mod = 10 ** 9 + 7
		dp = [[0] * (sum + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = pow(2, self.count_zeros_till_index(arr, i), mod)
		for i in range(1, n + 1):
			for j in range(1, sum + 1):
				if arr[i - 1] <= j:
					dp[i][j] = (dp[i - 1][j - arr[i - 1]] + dp[i - 1][j]) % mod
				else:
					dp[i][j] = dp[i - 1][j] % mod
		return dp[n][sum]


class Solution:

	def countSum(self, arr, index, sum, dp):
		if sum == 0 and index == len(arr):
			return 1
		if sum != 0 and index == len(arr):
			return 0
		if dp[index][sum] != -1:
			return dp[index][sum]
		notTake = self.countSum(arr, index + 1, sum, dp)
		take = 0
		if arr[index] <= sum:
			take = self.countSum(arr, index + 1, sum - arr[index], dp)
		dp[index][sum] = (take + notTake) % 1000000007
		return (take + notTake) % 1000000007

	def perfectSum(self, arr, n, sum):
		dp = [[int(-1) for col in range(sum + 1)] for row in range(n)]
		return self.countSum(arr, 0, sum, dp)


from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def perfectSum(self, arr, n, sum):
		MOD = 1000000000.0 + 7

		@lru_cache(None)
		def go(i, s):
			if s > sum:
				return 0
			if i == n:
				if s == sum:
					return 1
				return 0
			return go(i + 1, s) % MOD + go(i + 1, s + arr[i]) % MOD % MOD
		return int(go(0, 0) % MOD)


class Solution:

	def perfectSum(self, arr, n, sume):
		new = [i for i in arr if i != 0]
		table = [[-1] * (sume + 1) for i in range(n + 1)]

		def countsubsum(arr, K, n):
			if n == 0:
				return K == 0
			if K < 0:
				return 0
			if K == 0:
				return 1
			if table[n][K] == -1:
				count = 0
				count += countsubsum(arr, K, n - 1)
				if arr[n - 1] <= K:
					count += countsubsum(arr, K - arr[n - 1], n - 1)
				table[n][K] = count
			return table[n][K]
		count = 0
		for i in arr:
			if i == 0:
				count += 1
		ans = 2 ** count * countsubsum(new, sume, len(new))
		return ans % (10 ** 9 + 7)


class Solution:

	def perfectSum(self, arr, n, sum):
		dp = [[-1 for i in range(sum + 1)] for j in range(n + 1)]

		def solve(ind, k):
			if ind == n:
				if sum == k:
					return 1
				return 0
			if dp[ind][k] != -1:
				return dp[ind][k]
			if arr[ind] <= sum - k:
				dp[ind][k] = solve(ind + 1, k + arr[ind]) + solve(ind + 1, k)
			else:
				dp[ind][k] = solve(ind + 1, k)
			return dp[ind][k]
		return solve(0, 0) % (10 ** 9 + 7)


class Solution:

	def perfectSum(self, arr, n, s):
		count = 0
		dp = [[-1] * (s + 1) for i in range(n + 1)]
		mod = 10 ** 9 + 7
		dp[0][0] = 1
		for j in range(1, s + 1):
			dp[0][j] = 0
		for i in range(1, n + 1):
			for j in range(0, s + 1):
				if arr[i - 1] <= j:
					dp[i][j] = dp[i - 1][j - arr[i - 1]] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n][s] % mod


class Solution:

	def perfectSum(self, arr, n, sum):
		count = 0
		dp = [[-1 for i in range(sum + 1)] for j in range(n + 1)]
		return self.dfs(arr, n, sum, dp, count)

	def dfs(self, arr, n, sum, dp, count):
		if n == 0:
			if sum == 0:
				return 1
			else:
				return 0
		if dp[n][sum] != -1:
			return dp[n][sum]
		if arr[n - 1] <= sum:
			dp[n][sum] = (self.dfs(arr, n - 1, sum - arr[n - 1], dp, count) + self.dfs(arr, n - 1, sum, dp, count)) % (10 ** 9 + 7)
		else:
			dp[n][sum] = self.dfs(arr, n - 1, sum, dp, count) % (10 ** 9 + 7)
		return dp[n][sum]