模数子集和

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$ 和正整数 $m$。判断能否从中选择一个非空子序列，使所选元素之和能被 $m$ 整除。这里的子序列不要求连续，但每个位置至多选择一次。

输入格式

第一行两个整数 $n,m$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

存在符合条件的非空子序列则输出 YES，否则输出 NO。

样例输入 1

3 5
1 2 3

样例输出 1

YES

样例输入 2

1 6
5

样例输出 2

NO

数据范围

• $1\le n\le10^6$；
• $2\le m\le1000$；
• $0\le a_i\le10^9$。

本题采用独立测试点计分，每个测试点等分。

提示

当 $n\ge m$ 时，考虑前 $m$ 个数的 $m+1$ 个前缀和余数。