ガーナーのアルゴリズム
(math/garner.hpp)

#pragma once
#include<vector>
#include"mod_pow.hpp"

/**
 * 
 * @brief ガーナーのアルゴリズム
 *
 */

long long garner(const std::vector<long long>&a,const std::vector<long long>&mods){
    const int sz=a.size();
    long long coeffs[sz+1]={1,1,1,1};
    long long constants[sz+1]={};
    for(int i=0;i<sz;i++){
        long long v=(mods[i]+a[i]-constants[i])%mods[i]*mod_pow(coeffs[i],mods[i]-2,mods[i])%mods[i];
        for(int j=i+1;j<sz+1;j++) {
            constants[j]=(constants[j]+coeffs[j]*v)%mods[j];
            coeffs[j]=(coeffs[j]*mods[i])%mods[j];
        }
    }
    return constants[sz];
}

#line 2 "math/garner.hpp"
#include<vector>
#line 1 "math/mod_pow.hpp"
/**
 * @brief (x^y)%mod
 */

long long mod_pow(long long x,long long y,long long mod){
    long long ret=1;
    while(y>0) {
        if(y&1)(ret*=x)%=mod;
        (x*=x)%=mod;
        y>>=1;
    }
    return ret;
}
#line 4 "math/garner.hpp"

/**
 * 
 * @brief ガーナーのアルゴリズム
 *
 */

long long garner(const std::vector<long long>&a,const std::vector<long long>&mods){
    const int sz=a.size();
    long long coeffs[sz+1]={1,1,1,1};
    long long constants[sz+1]={};
    for(int i=0;i<sz;i++){
        long long v=(mods[i]+a[i]-constants[i])%mods[i]*mod_pow(coeffs[i],mods[i]-2,mods[i])%mods[i];
        for(int j=i+1;j<sz+1;j++) {
            constants[j]=(constants[j]+coeffs[j]*v)%mods[j];
            coeffs[j]=(coeffs[j]*mods[i])%mods[j];
        }
    }
    return constants[sz];
}