vector < int > vec[N];

int PrefixSum(vector < int >& vec , rig , lef)
{
    if(lef <= 0) return vec[rig];
    return vec[rig] - vec[lef-1];
}

int main()
{

    /// problem: https://lightoj.com/problem/coin-change-iii

    dpp[n+1][0] = 1;
    for(int rem = 1 ; rem <= m ; rem++) dpp[n+1][rem] = 0;

    for(int cur = n ; cur > 0 ; cur--){

        for(int i = 0 ; i < A[cur] ; i++) vec[i].clear();
//        for(int rem = 0 ; rem <= m ; rem){
//            vec[rem % mod].push_back(dpp[cur+1][rem]);
//        }

        for(int mod = 0 ; mod < A[cur] ; mod++){
            for(int rem = mod ; rem <= m ; rem += A[cur]){
                if(vec[mod].size() > 0){
                    vec[mod].push_back(vec[mod].back() + dpp[cur+1][rem]);
                }
                else vec[mod].push_back(dpp[cur+1][rem]); /// index = 0
            }
        }

        for(int mod = 0 ; mod < A[cur] ; mod++){
            for(int rem = mod , index = 0; rem <= m ; rem += A[cur] , index = index + 1){
                int sum = PrefixSum(vec[mod] , index , index - C[cur]);
                if(sum > 0) dpp[cur][rem] = 1;
                else dpp[cur][rem] = 0;
            }
        }


    }


}