Given a set of n non-negative integers, and a value m, determine if there is a subset of the given set with sum divisible by m.
Example 1:
Input: 
n = 4 m = 6 
nums[] = {3 1 7 5}
Output:
1
Explanation:
If we take the subset {7, 5} then sum
will be 12 which is divisible by 6.
Example 2:
Input:
n = 3, m = 5
nums[] = {1 2 6}
Output:
0
Explanation: 
All possible subsets of the given set are 
{1}, {2}, {6}, {1, 2}, {2, 6}, {1, 6}
and {1, 2, 6}. There is no subset whose
sum is divisible by 5.
Your Task:
You don't need to read or print anything. Your task is to complete the function DivisibleByM() which takes the given set and m as input parameter and returns 1 if any of the subset(non-empty) sum is divisible by m otherwise returns 0.
Expected Time Complexity: O(n*m)
Expected Space Complexity: O(n)
Constraints:
1 <= elements in set <= 1000
1 <= n, m <= 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
	def DivisibleByM(self, nums, m):
		# Code here

Solutions:
class Solution:

	def DivisibleByM(self, nums, m):

		def f(i, rem, nums, dp):
			if rem == 0:
				return True
			if i >= len(nums):
				return False
			if dp[i][rem] != -1:
				return dp[i][rem]
			if rem == -1:
				take = f(i + 1, nums[i] % m, nums, dp)
				ntake = f(i + 1, rem, nums, dp)
			else:
				take = f(i + 1, (rem + nums[i]) % m, nums, dp)
				ntake = f(i + 1, rem, nums, dp)
			dp[i][rem] = take or ntake
			return take or ntake
		dp = [[-1] * (m + 1) for _ in range(len(nums))]
		return int(f(0, -1, nums, dp))


class Solution:

	def DivisibleByM(self, arr, m):
		n = len(arr)
		if n > m:
			return 1
		DP = [False for i in range(m)]
		for i in range(n):
			if DP[0]:
				return 1
			temp = [False for i in range(m)]
			for j in range(m):
				if DP[j] == True:
					if DP[(j + arr[i]) % m] == False:
						temp[(j + arr[i]) % m] = True
			for j in range(m):
				if temp[j]:
					DP[j] = True
			DP[arr[i] % m] = True
		return int(DP[0])


class Solution:

	def DivisibleByM(self, nums, m):
		s = sum(nums)
		n = len(nums)
		t = [[0 for i in range(s + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			t[i][0] = 1
		for i in range(1, n + 1):
			for j in range(1, s + 1):
				if nums[i - 1] <= j:
					t[i][j] = t[i - 1][j - nums[i - 1]] or t[i - 1][j]
				else:
					t[i][j] = t[i - 1][j]
		for i in range(1, s + 1):
			if t[n][i] and i % m == 0:
				return 1
		return 0


class Solution:

	def DivisibleByM(self, a, m):
		n = len(a)
		v = [False] * n

		def solve(i, v, s):
			if i > n - 1:
				return False
			if (s + a[i]) % m == 0:
				return True
			if v[i]:
				return 0
			j = i + 1
			v[i] = True
			while j < n:
				if solve(j, v, s + a[i]):
					return True
				j += 1
			v[i] = False
		for i in range(n):
			if solve(i, v, 0):
				return 1
		return 0


class Solution:

	def DivisibleByM(self, nums, m):

		def solve(idx, data, d={}):
			if idx == len(nums):
				return False
			data += nums[idx]
			if data % m == 0:
				return True
			return solve(idx + 1, data, d) or solve(idx + 1, 0, d)
		return 1 if solve(0, 0) else 0


class Solution:

	def DivisibleByM(self, A, m):
		dp = [False for i in range(m)]
		n = len(A)
		if n > m:
			return 1
		for i in range(n):
			temp = [False for i in range(m)]
			for j in range(m):
				if dp[j] == True and dp[(j + A[i]) % m] == False:
					temp[(j + A[i]) % m] = True
			for p in range(m):
				if temp[p]:
					dp[p] = True
			dp[A[i] % m] = True
		return 1 if dp[0] else 0


class Solution:

	def subsetDivisible(self, n, nums, sum, idx, m, dp3):
		if idx == n:
			res = sum and sum % m == 0
			if res:
				dp3.add(sum)
				return 1
			return 0
		if sum in dp3:
			return 1
		picked = self.subsetDivisible(n, nums, sum + nums[idx], idx + 1, m, dp3)
		notPicked = self.subsetDivisible(n, nums, sum, idx + 1, m, dp3)
		return picked | notPicked

	def DivisibleByM(self, nums, m):

		def f(ind, sm):
			if sm > 0 and sm % m == 0:
				return 1
			if ind == -1:
				return 0
			return f(ind - 1, sm) or f(ind - 1, sm + nums[ind])
		return f(len(nums) - 1, 0)


class Solution:

	def subsetDivisible(self, n, nums, sum, idx, m, dp3):
		if idx == n:
			res = sum and sum % m == 0
			if res:
				dp3.add(sum)
				return 1
			return 0
		if sum in dp3:
			return 1
		picked = self.subsetDivisible(n, nums, sum + nums[idx], idx + 1, m, dp3)
		notPicked = self.subsetDivisible(n, nums, sum, idx + 1, m, dp3)
		return picked | notPicked

	def DivisibleByM(self, nums, m):
		dp3 = set()
		return self.subsetDivisible(len(nums), nums, 0, 0, m, dp3)


class Solution:

	def DivisibleByM(self, nums, m):

		def f(ind, sm):
			if sm > 0 and sm % m == 0:
				return 1
			if ind == -1:
				return 0
			return f(ind - 1, sm) or f(ind - 1, sm + nums[ind])
		return f(len(nums) - 1, 0)


class Solution:

	def DivisibleByM(self, nums, m):
		if len(nums) > m:
			return 1
		d = {}
		d[0] = 1
		c = 0
		s = 0
		for i in range(0, len(nums)):
			s += nums[i]
			rem = s % m
			if rem in d:
				c += d[rem]
				d[rem] += 1
			else:
				d[rem] = 1
		if c > 0:
			return 1
		else:
			return 0


class Solution:

	def DivisibleByM(self, nums, m):
		s = 0
		for i in nums:
			s = s + i
		dp = [[False for _ in range(s + 1)] for __ in range(len(nums) + 1)]
		for i in range(0, len(dp)):
			dp[i][0] = True
		for i in range(1, len(nums) + 1):
			for j in range(1, s + 1):
				if nums[i - 1] <= j:
					dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
				else:
					dp[i][j] = dp[i - 1][j]
				if j % m == 0 and dp[i][j]:
					return 1
		return 0


class Solution:

	def DivisibleByM(self, nums, m):

		def dfs(ss, nums, m):
			if ss < m:
				return False
			if ss % m == 0:
				return True
			for (idx, num) in enumerate(nums):
				val = dfs(ss - num, nums[:idx] + nums[idx + 1:], m)
				if val:
					return True
			return False
		ss = sum(nums)
		nums.insert(0, 0)
		cache = {}
		val = dfs(ss, nums, m)
		return val * 1


class Solution:

	def get(self, nums, m, s, N):
		if s % m == 0 and s != 0:
			return True
		if N == 0:
			return False
		return self.get(nums, m, s + nums[N - 1], N - 1) or self.get(nums, m, s, N - 1)

	def DivisibleByM(self, nums, m):
		if self.get(nums, m, 0, len(nums)):
			return 1
		return 0
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m) = input().split()
		n = int(n)
		m = int(m)
		nums = list(map(int, input().split()))
		ob = Solution()
		ans = ob.DivisibleByM(nums, m)
		print(ans)


class Solution:

	def DivisibleByM(self, nums, m):
		l = [0 for i in range(len(nums))]
		l = [nums[0]]
		dic = {}
		for i in range(m):
			dic[i] = []
		dic[nums[0] % m].append(0)
		for i in range(1, len(nums)):
			l.append(l[i - 1] + nums[i])
			dic[l[i] % m].append(i)
			if len(dic[l[i] % m]) > 1:
				return 1
			if len(dic[0]) > 0:
				return 1
		for i in range(m):
			if len(dic[i]) > 1:
				return 1
		return 0
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m) = input().split()
		n = int(n)
		m = int(m)
		nums = list(map(int, input().split()))
		ob = Solution()
		ans = ob.DivisibleByM(nums, m)
		print(ans)


class Solution:

	def DivisibleByM(self, nums, m):
		n = len(nums)

		def helper(ind, sums):
			if sums % m == 0 and sums != 0:
				return 1
			if ind < 0:
				return 0
			nott = helper(ind - 1, sums)
			take = helper(ind - 1, sums + nums[ind])
			return nott or take
		return helper(n - 1, 0)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m) = input().split()
		n = int(n)
		m = int(m)
		nums = list(map(int, input().split()))
		ob = Solution()
		ans = ob.DivisibleByM(nums, m)
		print(ans)


class Solution:

	def DivisibleByM(self, nums, m, i=0, cursum=0, memo=None):
		if not memo:
			memo = {}
		if (i, cursum) in memo:
			return memo[i, cursum]
		if cursum > 0 and cursum % m == 0:
			return 1
		if i >= len(nums):
			return 0
		result = self.DivisibleByM(nums, m, i + 1, cursum + nums[i], memo) or self.DivisibleByM(nums, m, i + 1, cursum, memo)
		memo[i, cursum] = result
		return result


class Solution:

	def DivisibleByM(self, nums, m):
		n = len(nums)
		tar = sum(nums)
		t = [[1 if i == 0 else 0 for i in range(tar + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, tar + 1):
				if nums[i - 1] <= j:
					t[i][j] = t[i - 1][j - nums[i - 1]] | t[i - 1][j]
				else:
					t[i][j] = t[i - 1][j]
		i = m
		while i <= tar:
			if t[-1][i]:
				return 1
			i += m
		return 0


class Solution:

	def DivisibleByM(self, nums, m):
		su = sum(nums)
		PG = [0 for i in range(su + 1)]
		PG1 = [0 for i in range(su + 1)]
		PG[0] = PG1[0] = 1
		for i in nums:
			for j in range(su + 1):
				if PG1[j] == 1:
					PG[j + i] = 1
					if (j + i) % m == 0:
						return 1
			PG1 = PG[:]
		return 0


class Solution:

	def sub_sum_div_by_m(self, arr, i, sum, m):
		if sum % m == 0 and sum != 0:
			return True
		if i >= len(arr):
			return False
		return self.sub_sum_div_by_m(arr, i + 1, sum, m) or self.sub_sum_div_by_m(arr, i + 1, sum + arr[i], m)

	def DivisibleByM(self, nums, m):
		if self.sub_sum_div_by_m(nums, 0, 0, m):
			return 1
		else:
			return 0


class Solution:

	def DivisibleByM(self, nums, m):
		nm = [[-1 for i in range(sum(nums) + 1)] for j in range(len(nums))]

		def dp(s, i, nm, n):
			if i == n:
				if s % m == 0 and s != 0:
					return True
				return False
			x = dp(s + nums[i], i + 1, nm, n)
			y = dp(s, i + 1, nm, n)
			return x or y
		return 1 if dp(0, 0, nm, len(nums)) else 0


class Solution:

	def checkDiv(self, nums, m, l, p):
		if l % m == 0 and p > 0:
			return True
		if p > 0:
			return self.checkDiv(nums, m, l - nums[p - 1], p - 1) or self.checkDiv(nums, m, l, p - 1)
		return False

	def DivisibleByM(self, nums, m):
		l = sum(nums)
		p = len(nums)
		z = self.checkDiv(nums, m, l, p)
		if z == True:
			return 1
		return 0


class Solution:

	def recur(self, nums, m, dp, sum, n):
		if sum % m == 0:
			return 1
		if n == 0:
			if sum % m == 0:
				return 1
			return 0
		if sum in dp.keys():
			return dp[sum]
		dp[sum] = self.recur(nums, m, dp, sum + nums[n - 1], n - 1) or self.recur(nums, m, dp, sum, n - 1)
		return dp[sum]

	def DivisibleByM(self, nums, m):
		dp = {}
		for i in range(len(nums) - 1, -1, -1):
			if self.recur(nums, m, dp, nums[i], i):
				return 1
		return 0


class Solution:

	def DivisibleByM(self, nums, m):
		mods = set()
		mods.add(0)
		for el in nums:
			el_mod = el % m
			for mod in list(mods):
				if (mod + el_mod) % m == 0:
					return 1
				mods.add((mod + el_mod) % m)
		return 0


class Solution:

	def DivisibleByM(self, nums, m):
		n = len(nums)
		dp = [[False for j in range(n)] for i in range(n)]
		for i in range(n):
			k = i
			for j in range(0, n - i):
				if i == 0:
					dp[j][k] = nums[j]
					if dp[j][k] % m == 0:
						return 1
				elif i == 1:
					dp[j][k] = nums[j] + nums[k]
					if dp[j][k] % m == 0:
						return 1
				else:
					dp[j][k] = nums[j] + dp[j + 1][k - 1] + nums[k]
					if (nums[j] + nums[k]) % m == 0:
						return 1
					elif dp[j][k] % m == 0:
						return 1
				k += 1
		return 0


class Solution:

	def DivisibleByM(self, nums, m):
		sum1 = sum(nums)
		dp = [0] * (sum1 + 1)
		for i in nums:
			set1 = set()
			for j in dp:
				if j not in set1:
					res = i + j
					if res % m == 0:
						return 1
					if dp[res] == 0:
						dp[res] = res
						set1.add(res)
					if dp[i] == 0:
						if i % m == 0:
							return 1
						dp[i] = i
		return 0


def subset(arr, n, m):
	t = []
	t = [[False for i in range(sum(arr) + 1)] for j in range(n + 1)]
	for i in range(n + 1):
		for j in range(sum(arr) + 1):
			if i == 0:
				t[i][j] = False
			if j == 0:
				t[i][j] = True
			elif arr[i - 1] <= j:
				t[i][j] = t[i - 1][j - arr[i - 1]] or t[i - 1][j]
			else:
				t[i][j] = t[i - 1][j]
	j = sum(arr)
	while j >= 1:
		if t[n][j] == True and j % m == 0:
			return 1
		j -= 1
	return 0

class Solution:

	def DivisibleByM(self, nums, m):
		n = len(nums)
		return subset(nums, n, m)


class Solution:

	def DivisibleByM(self, nums, m):
		memo = {}

		def helper(indx, val):
			if (indx, val) in memo:
				return memo[indx, val]
			if indx == len(nums):
				if val and val % m == 0:
					return 1
				return 0
			pick = helper(indx + 1, val + nums[indx])
			notpick = helper(indx + 1, val)
			memo[indx, val] = pick or notpick
			return memo[indx, val]
		return helper(0, 0)


class Solution:

	def DivisibleByM(self, nums, m):
		n = len(nums)
		for i in range(n):
			ts = nums[i]
			if ts % m == 0:
				return 1
			for j in range(i + 1, n):
				if (nums[j] + ts) % m == 0:
					return 1
				ts += nums[j]
		return 0


class Solution:

	def check(self, arr, n, m, s):
		dp = [[None for x in range(s + 1)] for y in range(n + 1)]
		for i in range(n + 1):
			for j in range(s + 1):
				if i == 0 and j != 0:
					dp[i][j] = False
				elif j == 0:
					dp[i][j] = True
				elif arr[i - 1] <= j:
					dp[i][j] = max(dp[i - 1][j - arr[i - 1]], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		res = False
		k = m
		while k <= s:
			for i in range(1, n + 1):
				res = max(res, dp[i][k])
			k += m
		return res

	def DivisibleByM(self, nums, m):
		if self.check(nums, len(nums), m, sum(nums)):
			return 1
		else:
			return 0


class Solution:

	def check(self, arr, n, m, s):
		if n == 0:
			if s != 0 and s % m == 0:
				return True
			return False
		return self.check(arr, n - 1, m, s + arr[n - 1]) or self.check(arr, n - 1, m, s)

	def DivisibleByM(self, nums, m):
		if m == 0:
			return 0
		if self.check(nums, len(nums), m, 0):
			return 1
		else:
			return 0


class Solution:

	def DivisibleByM(self, nums, m):

		def subset_sum_memo(memo: dict, array: list, sum: int, m: int, index: int) -> bool:
			if sum and sum % m == 0:
				return True
			elif index >= len(array):
				return False
			else:
				(value1, value2) = (False, False)
				if sum % m not in memo:
					value1 = subset_sum_memo(memo, array, sum + array[index], m, index + 1)
					value2 = subset_sum_memo(memo, array, sum, m, index + 1)
					if sum:
						memo[sum % m] = value1 or value2
				if not sum:
					return value1 or value2
				return memo[sum % m]
		if len(nums) >= m:
			return 1
		memo = {}
		return 1 if subset_sum_memo(memo, nums, 0, m, 0) else 0


class Solution:

	def devisibleby(self, arr, n, m, sum):
		if sum != 0 and sum % m == 0:
			return True
		if n <= 0:
			return False
		return self.devisibleby(arr, n - 1, m, sum) or self.devisibleby(arr, n - 1, m, sum + arr[n - 1])

	def DivisibleByM(self, nums, m):
		return 1 if self.devisibleby(nums, len(nums), m, 0) else 0


class Solution:

	def isSubsetSum(self, arr, n, sum):
		dp = [[0 for j 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(1, sum + 1):
				if arr[i - 1] > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j] or dp[i - 1][j - arr[i - 1]]
		return dp[n][sum]

	def devisibleby(self, arr, n, m, sum):
		if sum != 0 and sum % m == 0:
			return True
		if n <= 0:
			return False
		return self.devisibleby(arr, n - 1, m, sum) or self.devisibleby(arr, n - 1, m, sum + arr[n - 1])

	def DivisibleByM(self, nums, m):
		return 1 if self.devisibleby(nums, len(nums), m, 0) else 0


class Solution:

	def calculate(self, arr, i, Sum, m):
		if Sum % m == 0 and Sum != 0:
			return 1
		if i == len(arr):
			return 0
		return self.calculate(arr, i + 1, Sum + arr[i], m) or self.calculate(arr, i + 1, Sum, m)

	def DivisibleByM(self, nums, m):
		return self.calculate(nums, 0, 0, m)


class Solution:

	def DivisibleByM(self, nums, m):
		rangee = sum(nums)
		table = [[0] * (rangee + 1) for _ in range(n + 1)]
		for i in range(len(table)):
			table[i][0] = 1
		for i in range(1, len(table)):
			for j in range(1, len(table[0])):
				if nums[i - 1] <= j:
					table[i][j] = table[i - 1][j - nums[i - 1]] or table[i - 1][j]
				else:
					table[i][j] = table[i - 1][j]
		for i in range(m, len(table[0]), m):
			if table[-1][i]:
				return 1
		return 0


class Solution:

	def __init__(self):
		self.array = []
		self.allsum = 0

	def callmain(self, nums, total, n, m):
		if n < 0:
			return False
		if (self.allsum - total) % m == 0 and total != self.allsum:
			return True
		if self.array[n][total] != -1:
			return self.array[n][total]
		self.array[n][total] = self.callmain(nums, total - nums[n - 1], n - 1, m) or self.callmain(nums, total, n - 1, m)
		return self.array[n][total]

	def DivisibleByM(self, nums, m):
		total = sum(nums)
		self.allsum = total
		for i in range(len(nums) + 1):
			temp = []
			for j in range(total + 1):
				temp.append(-1)
			self.array.append(temp)
		x = self.callmain(nums, total, n, m)
		if x == True:
			return 1
		else:
			return 0


class Solution:

	def fun(self, nums, m, arr_pos):
		if curr_ind >= len(nums):
			return 0

	def DivisibleByM(self, nums, m, curr_ind=0, sum_val=0):
		if sum_val > 0:
			if sum_val % m == 0:
				return 1
		if curr_ind >= len(nums):
			return 0
		a = self.DivisibleByM(nums, m, curr_ind + 1, sum_val)
		return a or self.DivisibleByM(nums, m, curr_ind + 1, sum_val + nums[curr_ind])


class Solution:

	def DivisibleByM(self, nums, m):
		weights = nums
		n = len(weights)
		S = sum(weights)
		if S % m == 0:
			return 1
		if S < m:
			return 0
		S = sum(weights) // m * m
		dp = [[0] * (S + 1) for x in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, S + 1):
				if weights[i - 1] <= j:
					dp[i][j] = max(weights[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		for i in range(1, sum(weights) // m + 1):
			if dp[n][i * m] % m == 0 and dp[n][i * m] != 0:
				return 1
		return 0


class Solution:

	def DivisibleByM(self, nums, m):
		dp = []
		for i in range(2):
			dp.append([0] * m)
		for el in nums:
			c = el % m
			if dp[0][(m - c) % m] == 1:
				return 1
			for i in range(m):
				if dp[0][i] == 1:
					dp[1][i] = 1
					dp[1][(i + c) % m] = 1
			dp[1][c] = 1
			dp[0] = dp[1][:]
			dp[1] = [0] * m
		if dp[0][0] == 1:
			return 1
		else:
			return 0


class Solution:

	def DivisibleByM(self, arr, m):
		n = len(arr)
		sm = sum(arr)
		dp = [[0 for i in range(sm + 1)] for j in range(n + 1)]
		ans = 0
		for i in range(n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			for j in range(1, sm + 1):
				if arr[i - 1] > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j] or dp[i - 1][j - arr[i - 1]]
				if j % m == 0:
					ans = ans or dp[i][j]
		return ans


class Solution:

	def DivisibleByM(self, arr, m):
		if len(arr) > m:
			return 1
		dp = [False for _ in range(m)]
		for i in range(n):
			if dp[0]:
				return 1
			temp = [False for _ in range(m)]
			for j in range(m):
				if dp[j]:
					if not dp[(j + arr[i]) % m]:
						temp[(j + arr[i]) % m] = True
			for j in range(m):
				dp[j] = dp[j] or temp[j]
			dp[arr[i] % m] = True
		return int(dp[0])


class Solution:

	def DivisibleByM(self, nums, m):
		mod = [0 for i in range(m)]
		if len(nums) > m:
			return 1
		for i in range(len(nums)):
			temp = [0 for i in range(m)]
			if mod[0]:
				return 1
			for j in range(m):
				if mod[j]:
					if mod[(j + nums[i]) % m] == 0:
						temp[(j + nums[i]) % m] = 1
			temp[nums[i] % m] = 1
			for j in range(m):
				if temp[j]:
					mod[j] = temp[j]
		return mod[0]


class Solution:

	def DivisibleByM(self, nums, m):
		return 1 if self.calc(nums, len(nums), m, S=0) == True else 0

	def calc(self, nums, n, k, S):
		if S != 0 and S % k == 0:
			return True
		if n == 0:
			return False
		return self.calc(nums, n - 1, k, S) or self.calc(nums, n - 1, k, S - nums[n - 1])


def recursive(nums, m):
	dp = [[None] * (sum(nums) + 1) for _ in range(len(nums) + 1)]

	def solve(nums, index, m, total=0):
		if index == -1:
			return total and total % m == 0
		if dp[index + 1][total] is not None:
			return dp[index + 1][total]
		result = solve(nums, index - 1, m, total)
		dp[index + 1][total] = result or solve(nums, index - 1, m, total + nums[index])
		return dp[index + 1][total]
	return int(solve(nums, len(nums) - 1, m, 0))

def iterative(nums, m):
	total = sum(nums)
	dp = [0] * (total + 1)
	dp[0] = 1
	for i in range(len(nums)):
		for j in range(total, -1, -1):
			if nums[i] <= j:
				dp[j] = dp[j] or dp[j - nums[i]]
			if j and dp[j] and (j % m == 0):
				return 1
	return 0

class Solution:

	def DivisibleByM(self, nums, m):
		return iterative(nums, m)


import numpy

class Solution:

	def DivisibleByM(self, nums, m):
		n = len(nums)
		for i in range(n):
			for j in range(i, n):
				for k in range(j, n):
					if sum(nums[j:k + 1]) % m == 0:
						return 1
		return 0


class Solution:

	def DivisibleByM(self, nums, n):
		s = sum(nums)
		m = len(nums)
		dp = [[0] * (s + 1) for ele in range(m + 1)]
		for i in range(m + 1):
			dp[i][0] = 1
		for i in range(1, m + 1):
			for j in range(1, s + 1):
				dp[i][j] = dp[i - 1][j]
				if nums[i - 1] <= j:
					dp[i][j] = max(dp[i - 1][j - nums[i - 1]], dp[i - 1][j])
		for i in range(1, s + 1):
			if dp[m][i] and i % n == 0:
				return 1
		return 0


class Solution:

	def DivisibleByM(self, arr, m):
		n = len(arr)
		niz_b = [False for _ in range(m)]
		niz_a = [False for _ in range(m)]
		for j in range(1, n):
			for i in range(m):
				if (i - arr[j - 1]) % m == 0:
					niz_a[i] = True
				elif niz_b[(i - arr[j - 1]) % m]:
					niz_a[i] = True
				elif niz_b[i]:
					niz_a[i] = True
				else:
					niz_a[i] = False
			niz_b = [] + niz_a
		return int(niz_b[-arr[n - 1] % m] or niz_b[0])