You are given a sequence of numbers a_1, a_2, ..., a_{n}, and a number m.

Check if it is possible to choose a non-empty subsequence a_{i}_{j} such that the sum of numbers in this subsequence is divisible by m.


-----Input-----

The first line contains two numbers, n and m (1 ≤ n ≤ 10^6, 2 ≤ m ≤ 10^3) — the size of the original sequence and the number such that sum should be divisible by it.

The second line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9).


-----Output-----

In the single line print either "YES" (without the quotes) if there exists the sought subsequence, or "NO" (without the quotes), if such subsequence doesn't exist.


-----Examples-----
Input
3 5
1 2 3

Output
YES

Input
1 6
5

Output
NO

Input
4 6
3 1 1 3

Output
YES

Input
6 6
5 5 5 5 5 5

Output
YES



-----Note-----

In the first sample test you can choose numbers 2 and 3, the sum of which is divisible by 5.

In the second sample test the single non-empty subsequence of numbers is a single number 5. Number 5 is not divisible by 6, that is, the sought subsequence doesn't exist.

In the third sample test you need to choose two numbers 3 on the ends.

In the fourth sample test you can take the whole subsequence.

Difficulty: interview

Starter code:

Solutions:
__author__ = 'User'
n, m = list(map(int, input().split()))
arr = list(map(int, input().split()))
for i in range(n):
    arr[i] = arr[i] % m
d = [0] * m
for e in arr:
    t = [0] * m
    t[e] = 1
    for i in range(m):
        if d[i] == 1:
            #print("T", i + e)
            t[(i + e) % m] = 1
    for i in range(m):
        if t[i] == 1:
            d[i] = 1
    #print(d)
    if d[0] == 1:
        break
if d[0] == 1:
    print("YES")
else:
    print("NO")
#print(d)
#print(arr)


(n,m)=map(int,input().split())
if n>2*m:print("YES")
else:
	t=[0 for i in range(m)]
	s=input().split()
	for i in range(len(s)):
		h=int(s[i])%m
		v=[0 for i in range(m)]
		for j in range(m):
			if t[j]==1:v[(h+j)%m]=1
		for j in range(m):
			if v[j]==1:t[j]=1
		t[h]=1
	if t[0]==1:print("YES")
	else:print("NO")

from copy import deepcopy
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
if n > m:
    print('YES')
else:
    d = [False for i in range(m)]
    b = [False for i in range(m)]
    for i in range(n):
        for j in range(m):
            if d[j] == True:
                b[(j + a[i]) % m] = True
        b[a[i] % m] = True
        for j in range(m):
            if b[j] == True:
                d[j] == True
        d = deepcopy(b)
    if d[0] == True:
        print('YES')
    else:
        print('NO')


def main():
    n, m = map(int, input().split())
    mas = list(map(int, input().split()))
    
    remains = set()
    
    for i in range(n):
        for_add = set()
        for e in remains:
            if (e + mas[i]) % m == 0:
                return True
            else:
                for_add.add((e + mas[i]) % m)
        
        if mas[i] % m == 0:
            return True
        else:
            for_add.add(mas[i])
            
        remains |= for_add

if main():
    print("YES")
else:
    print("NO")

#import sys
#sys.stdin = open("python/in", "r")

#n = int(input().split(" "))
n, m = [int (i) for i in input().split(" ")]
arr = [int (i) % m for i in input().split(" ")]

c = {}
for i in range(m):
    c[i] = False

stack = [0]
newstack = []

for i in arr:
    for j in stack:
        arrrrgh = (i+j) % m
        if (arrrrgh == 0):
            print ("YES")
            return
        elif (c[arrrrgh] == False):
            newstack.append(arrrrgh)
            c[arrrrgh] = True
    stack = stack + newstack
    newstack = []

print("NO")


n, m = (int(x) for x in input().split())
lst = [int(x) for x in input().split()]
cnt = [0 for i in range(m)]

if n > m:
	print("YES")
	return

for x in lst:
	cnt[x % m] += 1

tbl = [[False for j in range(n + 1)] for i in range(m)]

#print(tbl)

tbl[0][0] = True

for j in range(1, n + 1):
	for i in range(m):
		tbl[i][j] = tbl[i][j-1]

	for i in range(m):
		#print(i, j)
		if tbl[i][j - 1]:
			if (i + lst[j - 1]) % m == 0:
				print("YES")
				return 
			tbl[(i + lst[j - 1]) % m][j] = True 

print("NO")


n, m = [int(i) for i in input().split()]
r = [False] * m
for x in [int(i)%m for i in input().split()]:
    c = r.copy()
    c[x] = True
    for i in range(m):
        if r[i]:
            c[(i+x)%m] = True
    r = c.copy()
    if r[0]:
        print("YES")
        return
print("NO")

__author__ = 'dwliv_000'
(n,m)=(int(i) for i in input().split())
c=[int(i)%m for i in  input().split()]
z=[False]*m
for j in c:
    q=z[:]
    q[j]=True
    for i in range(m):
        if(z[i]):
            q[(i+j)%m]=True
    z=q[:]
    if z[0]:
        print('YES')
        return
print('NO')



n,m=list(map(int,input().split()))
l=list(map(int,input().split()))
if n>m: print("YES")
else:
    d=[{},{}]
    cur=0
    for x in l:
        for y in list(d[cur].keys()): 
            d[1-cur][y]=1
            d[1-cur][(y+x)%m]=1
        cur=1-cur
        d[cur][x%m]=1
        if d[cur].get(0,0): break
    print("YES" if d[cur].get(0,0) else "NO")


#!/usr/bin/env python
# 577B_modulo.py - Codeforces.com/problemset/problem/577/B by Sergey 2015

import unittest
import sys

###############################################################################
# Modulo Class (Main Program)
###############################################################################


class Modulo:
    """ Modulo representation """

    def __init__(self, test_inputs=None):
        """ Default constructor """

        it = iter(test_inputs.split("\n")) if test_inputs else None

        def uinput():
            return next(it) if it else sys.stdin.readline().rstrip()

        # Reading single elements
        [self.n, self.m] = list(map(int, uinput().split()))

        # Reading a single line of multiple elements
        self.nums = list(map(int, uinput().split()))

        # Modulo
        self.modnums = [v % self.m for v in self.nums]

        # Frequency counter
        self.cnt = {}
        self.vars = {}
        for v in self.modnums:
            if v not in list(self.cnt.keys()):
                self.cnt[v] = 0
                self.vars[v] = []
            self.cnt[v] += 1

    def calculate(self):
        """ Main calcualtion function of the class """

        # For multiples
        for v in list(self.vars.keys()):
            cur = v
            for j in range(self.cnt[v]):
                if j > (v * self.m):
                    break
                self.vars[v].append(cur)
                if cur == 0:
                    return "YES"
                cur = (cur + v) % self.m

        # Collect sum
        cur = set([0])
        for var in list(self.vars.keys()):
            for s in set(cur):
                for v in self.vars[var]:
                    if v == 0:
                        return "YES"
                    res = v + s
                    if res == self.m:
                        return "YES"
                    cur.add(res % self.m)

        return "NO"

###############################################################################
# Unit Tests
###############################################################################


class unitTests(unittest.TestCase):

    def test_single_test(self):
        """ Modulo class testing """

        # Constructor test
        test = "3 5\n1 2 3 3"
        d = Modulo(test)
        self.assertEqual(d.n, 3)
        self.assertEqual(d.m, 5)
        self.assertEqual(d.nums, [1, 2, 3, 3])

        # Sample test
        self.assertEqual(Modulo(test).calculate(), "YES")

        # Sample test
        test = "1 6\n5"
        self.assertEqual(Modulo(test).calculate(), "NO")

        # Sample test
        test = "4 6\n3 1 1 3"
        self.assertEqual(Modulo(test).calculate(), "YES")

        # My tests
        test = "6 6\n5 5 5 5 5 5"
        self.assertEqual(Modulo(test).calculate(), "YES")

        test = "4 5\n1 1 1 1"
        self.assertEqual(Modulo(test).calculate(), "NO")

        # Time limit test
        self.time_limit_test(1000000)

    def time_limit_test(self, nmax):
        """ Timelimit testing """
        import random
        import timeit

        # Random inputs
        test = str(nmax) + " " + str(405) + "\n"
        nums = [random.randint(1, 10000000) for i in range(nmax)]
        test += " ".join(map(str, nums)) + "\n"

        # Run the test
        start = timeit.default_timer()
        d = Modulo(test)
        calc = timeit.default_timer()
        d.calculate()
        stop = timeit.default_timer()
        print(("\nTimelimit Test: " +
              "{0:.3f}s (init {1:.3f}s calc {2:.3f}s)".
              format(stop-start, calc-start, stop-calc)))

def __starting_point():

    # Avoiding recursion limitaions
    sys.setrecursionlimit(100000)

    if sys.argv[-1] == "-ut":
        unittest.main(argv=[" "])

    # Print the result string
    sys.stdout.write(Modulo().calculate())

__starting_point()

n, m = list(map(int, input().split()))

seen = set()
for a in map(int, input().split()):
    new = set()
    for b in seen:
        new.add((a+b) % m)
    seen |= new
    seen.add(a % m)
    if 0 in seen:
        print('YES')
        break
else:
    print('NO')


#!/usr/bin/env python3
"""
Codeforces Round #319 (Div. 2)

Problem 577 B. Modulo Sum

@author yamaton
@date 2015-09-10
"""

import itertools as it
import functools
import operator
import collections
import math
import sys

def solve(xs, m):
    modulos = set()
    for x in xs:
        modulos |= {(x + i) % m for i in modulos}
        modulos.add(x % m)
        if 0 in modulos:
            return True
    else:
        return False

def tf_to_yn(tf):
    return 'YES' if tf else 'NO'


def print_stderr(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


def main():
    [n, m] = [int(i) for i in input().strip().split()]    
    xs = [int(i) for i in input().strip().split()]
    assert len(xs) == n

    result = solve(xs, m)
    print(tf_to_yn(result))


def __starting_point():
    main()

__starting_point()

def dp(n,m):
    mark = [0 for i in range(m)]
    a = list(map(int,input().split()))
    for x in a:
        for i in range(m):
            if(mark[i]==1):
                k=(i+x%m)%m
                if(mark[k]!=1):
                    mark[k]=2
        for i in range(m):
            if(mark[i]>0):
                mark[i]=1
        mark[x%m]=1
    return mark[0]
import sys
input = sys.stdin.readline
n,m = list(map(int,input().split()))
flag = True
if(n<=m):
    flag=(dp(n,m)!=0)
if(flag):
    print("YES")
else:
    print("NO")


#!/usr/bin/env python
# 577B_modulo.py - Codeforces.com/problemset/problem/577/B by Sergey 2015

import unittest
import sys

###############################################################################
# Modulo Class (Main Program)
###############################################################################


class Modulo:
    """ Modulo representation """

    def __init__(self, test_inputs=None):
        """ Default constructor """

        it = iter(test_inputs.split("\n")) if test_inputs else None

        def uinput():
            return next(it) if it else sys.stdin.readline().rstrip()

        # Reading single elements
        [self.n, self.m] = list(map(int, uinput().split()))

        # Reading a single line of multiple elements
        self.nums = list(map(int, uinput().split()))

        # Modulo
        self.modnums = [v % self.m for v in self.nums]

        # Frequency counter
        self.cnt = {}
        self.vars = {}
        for v in self.modnums:
            if v not in list(self.cnt.keys()):
                self.cnt[v] = 0
                self.vars[v] = set([])
            self.cnt[v] += 1

    def calculate(self):
        """ Main calcualtion function of the class """

        # For multiples
        for v in list(self.vars.keys()):
            cur = v
            for j in range(self.cnt[v]):
                if cur in self.vars[v]:
                    break
                self.vars[v].add(cur)
                if cur == 0:
                    return "YES"
                cur = (cur + v) % self.m

        # Collect sum
        cur = set([0])
        for var in list(self.vars.keys()):
            for s in set(cur):
                for v in self.vars[var]:
                    res = v + s
                    if res == self.m:
                        return "YES"
                    cur.add(res % self.m)

        return "NO"

###############################################################################
# Unit Tests
###############################################################################


class unitTests(unittest.TestCase):

    def test_single_test(self):
        """ Modulo class testing """

        # Constructor test
        test = "3 5\n1 2 3 3"
        d = Modulo(test)
        self.assertEqual(d.n, 3)
        self.assertEqual(d.m, 5)
        self.assertEqual(d.nums, [1, 2, 3, 3])

        # Sample test
        self.assertEqual(Modulo(test).calculate(), "YES")

        # Sample test
        test = "1 6\n5"
        self.assertEqual(Modulo(test).calculate(), "NO")

        # Sample test
        test = "4 6\n3 1 1 3"
        self.assertEqual(Modulo(test).calculate(), "YES")

        # My tests
        test = "6 6\n5 5 5 5 5 5"
        self.assertEqual(Modulo(test).calculate(), "YES")

        test = "4 5\n1 1 1 1"
        self.assertEqual(Modulo(test).calculate(), "NO")

        # Time limit test
        self.time_limit_test(10000)

    def time_limit_test(self, nmax):
        """ Timelimit testing """
        import random
        import timeit

        # Random inputs
        test = str(nmax) + " " + str(990) + "\n"
        nums = [random.randint(2, 990) for i in range(nmax)]
        test += " ".join(map(str, nums)) + "\n"

        # Run the test
        start = timeit.default_timer()
        d = Modulo(test)
        calc = timeit.default_timer()
        d.calculate()
        stop = timeit.default_timer()
        print(("\nTimelimit Test: " +
              "{0:.3f}s (init {1:.3f}s calc {2:.3f}s)".
              format(stop-start, calc-start, stop-calc)))

def __starting_point():

    # Avoiding recursion limitaions
    sys.setrecursionlimit(100000)

    if sys.argv[-1] == "-ut":
        unittest.main(argv=[" "])

    # Print the result string
    sys.stdout.write(Modulo().calculate())

__starting_point()

def main():
    n, m = list(map(int, input().split()))
    l = [False] * m
    l1 = l.copy()
    for i in map(int, input().split()):
        i %= m
        l1[i] = True
        for j, f in enumerate(l, i - m):
            if f:
                l1[j] = True
        if l1[0]:
            print("YES")
            return
        l = l1.copy()
    print("NO")


def __starting_point():
    main()

__starting_point()

def main():
    n, m = list(map(int, input().split()))
    l = [False] * m
    l1 = l.copy()
    for i in map(int, input().split()):
        i %= m
        l1[i] = True
        for j, f in enumerate(l, i - m):
            if f:
                l1[j] = True
        if l1[0]:
            print("YES")
            return
        for j, f in enumerate(l1):
            if f:
                l[j] = True
    print("NO")


def __starting_point():
    main()

__starting_point()

n , m = list(map(int, input().split()))
lst = list(map(int, input().split()))
ans = set()
for i in lst:
    if ans:
        for j in ans.copy():
            ans.add((i + j) % m)
            ans.add(i % m)
            
    else:
        ans.add(i % m)
    if 0 in ans:
        print('YES')
        break
else:
    print('NO')
    


n , m = list(map(int, input().split()))
lst = list(map(int, input().split()))
ans = set()
for i in lst:
    if ans:
        for j in ans.copy():
            ans.add((i + j) % m)
            ans.add(i % m)
            
    else:
        ans.add(i % m)
    if 0 in ans:
        print('YES')
        break
else:
    print('NO')
    


n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
rem = set()
for i in a:
    new = {(i + j) % m for j in rem | {0}}
    rem |= new
    if 0 in rem:
        print('YES')
        return
print('NO')


def main():
    n, m = [int(i) for i in input().split()]
    if n > m:
        print("YES")
        return
    a = [int(i) % m for i in input().split()]
    d = [False] * m
    for i in a:
        next = d[:]
        for j in range(m):
            k = j + i
            if k >= m: k -= m
            next[k] = d[k] or d[j]
        d = next
        d[i] = True
    if d[0]:
        print("YES")
    else:
        print("NO")
    
    
    
main()


#!/usr/bin/env python3
import sys

N, M = input().split()
A = list(map(int, input().split()))
N = int(N)
M = int(M)

if N > M:
  print('YES')
  return

sys.setrecursionlimit(2000)

Q_memo = {}

for i, a in enumerate(A):
  A[i] = A[i] % M

def Q(i, K, empty_sequence_ok):
  # true if there exists a subset of (A[0]...A[i]) that sums to K

  # print('Q(%d, %d, %r)' % (i, K, empty_sequence_ok))

  if empty_sequence_ok and K == 0: return True
  if i == 0: return A[0] == K

  args = (i, K, empty_sequence_ok)
  if args not in Q_memo:
    Q_memo[args] = Q(i - 1, K, empty_sequence_ok) or Q(i - 1, (K - A[i]) % M, True)
  return Q_memo[args]

if Q(N-1, 0, False):
  print('YES')
else:
  print('NO')

n, m = (int(i) for i in input().split())
numbers = [int(i) for i in input().split()]
results = {0}

res_update = results.update

for i in numbers:
    tmp_results = set()
    for j in results:
        if (j+i) % m == 0:
            print('YES')
            return
        tmp_results.add((j+i) % m)
    res_update(tmp_results)
print('NO')




n, m = map(int, input().split())
a = list(map(int, input().split()))
rem = set()
for i in a:
    new = {(i + j) % m for j in rem | {0}}
    rem |= new
    if 0 in rem:
        print('YES')
        return
print('NO')


# -*- coding: utf-8 -*-

n, m = list(map(int,input().split()))
p = [0]*m
for x in map(int,input().split()):
    n = p[:]
    n[x%m] = 1
    for i in range(m):
        if p[i] == 1:
            n[(i+x)%m] = 1
    p = n
    if p[0]:
        print('YES')
        return

print('NO')



n, m = list(map(int, input().split()))
a = list([x%m for x in list(map(int, input().split()))])
h = {}

for el in a:
    h[el] = h.get(el, 0) + 1

for v in list(h.values()):
    if v % m == 0:
        print("YES")
        return

possible = set([])
for el in a:
    new = set([el])
    for candidate in possible:
       new.add((candidate + el)%m)

    possible |= new
    if 0 in possible:
        print("YES")
        return
print("NO")