#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include #include #include #include using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(i64 i=0; i void chmin(A& l, const A& r){ if(r < l) l = r; } template void chmax(A& l, const A& r){ if(l < r) l = r; } using namespace std; #include #include namespace nachia{ // ax + by = gcd(a,b) // return ( x, - ) std::pair ExtGcd(long long a, long long b){ long long x = 1, y = 0; while(b){ long long u = a / b; std::swap(a-=b*u, b); std::swap(x-=y*u, y); } return std::make_pair(x, a); } } // namespace nachia namespace nachia{ class DynamicModSupplier{ using u64 = unsigned long long; using Int = unsigned int; private: u64 imod; Int mod; // atcoder library u64 reduce2(u64 z) const noexcept { // atcoder library #ifdef _MSC_VER u64 x; _umul128(z, im, &x); #else using u128 = unsigned __int128; u64 x = (u64)(((u128)(z)*imod) >> 64); #endif return z - x * mod; } public: DynamicModSupplier(unsigned int MOD = 998244353) : mod(MOD) { assert(2 <= MOD); assert(MOD < (1u << 31)); imod = (u64)(-1) / mod + 1; } Int reduce(u64 z) const noexcept { Int v = reduce2(z); if(mod <= v) v += mod; return v; } Int add(Int a, Int b) const { a += b; if(a >= mod){ a -= mod; } return a; } Int sub(Int a, Int b) const { a -= b; if(a >= mod){ a += mod; } return a; } Int mul(Int a, Int b) const { return reduce((u64)a * b); } Int muladd(Int a, Int b, Int c) const { return reduce((u64)a * b + c); } Int inv(Int a) const { Int v = ExtGcd(a, mod).first; return (v < mod) ? v : (v + mod); } Int pow(Int a, u64 i) const { Int r = a, ans = 1; while(i){ if(i & 1) ans = mul(ans, r); i /= 2; r = mul(r, r); } return ans; } Int getMod() const { return mod; } }; } // namespace nachia namespace nachia{ template struct GarnerMod{ using Int = unsigned int; using IntLong = unsigned long long; std::vector mods; std::vector dynmods; std::vector> table_coeff; std::vector table_coeffinv; void precalc(std::vector new_mods){ mods = std::move(new_mods); dynmods.resize(mods.size()); for(size_t i=0; i(nmods, 1)); for(int j=0; j& x) const { int nmods = mods.size(); std::vector table_const(nmods); FinishType res = 0; FinishType res_coeff = 1; for(int j=0; j calc(std::vector> x) const { int n = x[0].size(), m = x.size(); std::vector res(n); std::vector buf(m); for(int i=0; i> N; N++; vector P(3), Q(3); rep(i,3) cin >> P[i]; rep(i,3) cin >> Q[i]; i64 prod = (i64)P[0] * P[1] * P[2]; rep(i,P.size()) if(P[i] == 1){ P.erase(P.begin() + i); Q.erase(Q.begin() + i); i--; } auto ds = nachia::GarnerMod(); ds.precalc(P); i64 f = ds.calc(Q); i64 ans = N / prod; if(f < N % prod) ans++; cout << ans << "\n"; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); testcase(); return 0; }