Modulo Sum

题意翻译

# 题面描述 给出 $1$ 个长度为 $n$ 的序列,以及 $1$ 个正整数 $m$。问这个原序列中是否存在非空子序列,使其元素之和能被 $m$ 整除。 # 输入格式 第 $1$ 行,有 $2$ 个正整数,分别为原序列的长度 $n$ 和 除数 $m$。 (数据范围:$1 \leqslant n \leqslant 10^{6}$,$2 \leqslant m \leqslant 10^{3}$) 第 $2$ 行,有 $n$ 个自然数,表示该原序列的元素 $a_i$。 (数据范围:$0 \leqslant a_i \leqslant 10^{9}$) # 输出格式 仅 $1$ 行,如果存在符合条件的子序列,输出 **YES**,否则输出 **NO**。 # 样例解释 - 第 $1$ 组样例的解释: 存在符合条件的子序列 $\{2,3\}$,其元素之和为 $2 + 3 = 5$,$5$ 可以被 $5$ 整除。 - 第 $2$ 组样例的解释: 由于原序列中只有 $1$ 个元素,因此它只有 $1$ 个子序列 $\{5\}$,但显然 $5$ 不可以被 $6$ 整除。 - 第 $3$ 组样例的解释: 存在符合条件的子序列 $\{3,3\}$,其元素之和为 $3 + 3 = 6$,$6$ 可以被 $6$ 整除。 - 第 $4$ 组样例的解释: 选择整个原序列作为子序列,其元素之和为 $5 + 5 + 5 + 5 + 5 + 5 = 30$,$30$ 可以被 $6$ 整除。 Translated by Sooke

题目描述

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_{ij} $ such that the sum of numbers in this subsequence is divisible by $ m $ .

输入输出格式

输入格式


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} $ ).

输出格式


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.

输入输出样例

输入样例 #1

3 5
1 2 3

输出样例 #1

YES

输入样例 #2

1 6
5

输出样例 #2

NO

输入样例 #3

4 6
3 1 1 3

输出样例 #3

YES

输入样例 #4

6 6
5 5 5 5 5 5

输出样例 #4

YES

说明

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.