CF577B Modulo Sum

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

N/A

N/A

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.