ChineseRemainTheory

struct Pair
{
    /*x = a (mod p)
    first = a
    second = p = v^k
    third = phi(p)
    */
    ll first, second, third;
    Pair(ll x = 0, ll y = 0, ll z = 0) : first(x), second(y), third(z) {}
};


ll Pow(ll a, ll b, ll mod)
{
    a %= mod;
    ll ans(1);
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
    }
    return ans;
}

ll ChineseRemainTheory(vector<Pair> s)
{
    ll ans(0), mod(1);
    for (auto i : s)
        mod *= i.second;
    vector<ll> pref(s.size()), suf(s.size());
    for (int i = 0; i < (int)s.size(); ++i)
    {
        pref[i] = i == 0 ? s[i].second : (pref[i - 1] * s[i].second % mod);
        suf[s.size() - 1 - i] = i == 0 ? s[s.size() - 1].second : (suf[s.size() - i] * s[s.size() - 1 - i].second % mod);
    }
    for (int i = 0; i < (int)s.size(); ++i)
    {
        //cout << s[i].first << " " << s[i].second << " " << s[i].third << "\n";
        ll tmp(s[i].first), tmp2(1);
        tmp = (tmp2 = (i == 0 ? 1 : pref[i - 1]) * (i < (int)s.size() - 1 ? suf[i + 1] : 1) % mod) * s[i].first % mod;
        (ans += tmp * Pow(tmp2, s[i].third - 1, mod)) %= mod;
    }
    return ans;
}