You are given a sequence of numbers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>, and a number *m*.

Check if it is possible to choose a non-empty subsequence *a*<sub class="lower-index">*i*<sub class="lower-index">*j*</sub></sub> 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<sup class="upper-index">6</sup>, 2 ≤ *m* ≤ 10<sup class="upper-index">3</sup>) — the size of the original sequence and the number such that sum should be divisible by it.

The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>).
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int recurr(int n, int i, int m, int score, vector<int> &dp, int arr[]){
    if (!(score % m) && score) return 1;
    if (i >= n) return 0;
    if (dp[i]) return dp[i];
    int take = recurr(n, i+1, m, score+arr[i], dp, arr), notTake = recurr(n, i+1, m, score, dp, arr);
    return dp[i] = take + notTake;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    string ans="NO";
    int arr[n];
    for (int i = 0; i < n; i++){
        int temp; cin >> temp;
        arr[i] = temp;
        ans = (!temp ? "YES" : "NO");
    }
    if (ans == "YES") cout << ans << endl;
    else{
        vector<int> dp(n+1, 0);
        cout << (recurr(n, 0, m, 0, dp, arr) ? "YES" : "NO");
    }


}