#include <iostream>
#include <vector>

int euclid(int a, int b, int& x, int& y) 
{
    int x1 = 0; x = 1;
    int y1 = 1; y = 0;

    while (b > 0) {
        int q = a / b;

        std::tie(x, x1) = std::make_tuple(x1, x - q * x1);
        std::tie(y, y1) = std::make_tuple(y1, y - q * y1);
        std::tie(a, b ) = std::make_tuple( b, a - q * b );
    }

    return a;
}

int mod(int a, int m) 
{
    if (a >= 0) return a % m;
    return (m + (a % m)) % m;
}

int mod_plus(int a, int b, int m)
{
    return mod(mod(a, m) + mod(b, m), m);
}

int mod_times(int a, int b, int m)
{
    return mod(mod(a, m) * mod(b, m), m);
}

int mul_inv(int a, int n) 
{
    int x, y;
    int d = euclid(a, n, x, y);

    if (d != 1) return -1;

    return mod(x, n);
}

int crt(const std::vector<int> &a, const std::vector<int> &n)
{
    int N = 1;
    for (int i = 0; i < n.size(); i++) 
        N *= n[i];

    int x = 0;

    for (int i = 0; i < a.size(); i++) {
        int mi = N / n[i];
        int ci = mod_times(mi, mul_inv(mi, n[i]), N);

        x = mod_plus(x, mod_times(a[i], ci, N), N);
    }

    return x;
}

int main(void) 
{
    std::vector<int> a = { 2, 3, 2 };
    std::vector<int> n = { 3, 5, 7 };

    std::cout << crt(a, n) << std::endl;

    return 0;
}