#include #include using namespace std; using ull = unsigned long long; using ll = long long; using xy = pair; using coord = pair; using bs8 = bitset<8>; using bs16 = bitset<16>; using bs32 = bitset<32>; using bs64 = bitset<64>; using vl = vector; using vvl = vector; using vvvl = vector; using vd = vector; using vvd = vector; using vs = vector; using vvs = vector; using vxy = vector; using vvxy = vector; using vcoord = vector; using vvcoord = vector; #define rep(var, n) for (ll var = 0; var < (ll)(n); var++) #define cnt(var, n, m) for (ll var = (n); var <= (ll)(m); var++) #define rcnt(var, n, m) for (ll var = (n); var >= (ll)(m); var--) #define each(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++) #define reach(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++) #define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl; #define ZINIT 1 #if __has_include("zout.h") #include "zout.h" #else namespace zz_print { class dbg { public: static bool unprint; static string margin; static string separated; static string indentS; static int hierarchical; static int topHier; static int precision; static bool exponential; static void setFloat(const int& prec, const bool& expo) { precision = prec; exponential = expo; }; template static void zout(Args&&... args) {}; }; bool dbg::unprint = false; string dbg::margin = ""; string dbg::separated = ""; string dbg::indentS = ""; int dbg::hierarchical = 0; int dbg::topHier = 0; int dbg::precision = 6; bool dbg::exponential = false; }; // namespace zz_print using namespace zz_print; #endif xy gcdex(const ll a, const ll b) { xy ans; if (abs(a) < abs(b)) { ans = gcdex(b, a); swap(ans.first, ans.second); return ans; } else if (b == 0) { return xy{1, 0}; } // a > b // da x + db y = d // a x + b y = 1 // (b(a/b) + a%b) x + b y = 1 // b ((a/b)x + y) + a%b x = 1 // b x' + a%b y' = 1 // // |x| | 0 1 | |x'| // | | = | |*| | // |y| | 1 -a/b | |y'| // ans = gcdex(b, a % b); return xy{ans.second, ans.first - (a / b) * ans.second}; }; xy gcdex(const xy ab) { return gcdex(ab.first, ab.second); } ll gcd(const ll a, const ll b) { xy ans = gcdex(a, b); return abs(a * ans.first + b * ans.second); } ll gcd(const xy ab) { return gcd(ab.first, ab.second); } ll gcd(const vl& vec) { ll n = vec.size(); if (n == 0) return 1; if (n == 1) return vec[0]; vl subvec; rep(i, n / 2) subvec.push_back(gcd(vec[2 * i], vec[2 * i + 1])); if (n % 2) subvec.push_back(vec[n - 1]); return gcd(subvec); } ll lcm(const ll a, const ll b) { return (a * (b / gcd(a, b))); } ll lcm(const xy ab) { return lcm(ab.first, ab.second); } ll lcm(const vl& vec) { ll n = vec.size(); if (n == 0) return 1; if (n == 1) return vec[0]; vl subvec; rep(i, n / 2) subvec.push_back(lcm(vec[2 * i], vec[2 * i + 1])); if (n % 2) subvec.push_back(vec[n - 1]); return lcm(subvec); } xy ganner(const vxy& vec) { ll n = vec.size(); if (n == 0) return xy{-1, 0}; if (n == 1) return vec[0]; vxy subvec; rep(i, n / 2) { ll r1 = vec[2 * i].first, r2 = vec[2 * i + 1].first; ll p1 = vec[2 * i].second, p2 = vec[2 * i + 1].second; // p1 * x + p2 * y = d [%lcm(p1,p2)] // d*p1' * x + d*p2' * y = d [%(p1*p2/d)] // (d*p1' * x + d*p2' * y) * ((r2 - r1)/d) = d * ((r2 - r1)/d) [%(p1*p2/d)] // s * p1 * x + s * p2 * y = r2 - r1 [%(p1*p2/d)] // r1 + (s * x) * p1 = r2 - (s * p2) * y [%(p1*p2/d)] // // d*s = r2 - r1 [%p2] // s = (r2 - r1)/d [%(p2/d)] // x = d * 1 / p1 [%p2] // x = 1 / p1' [%p2] // x = inv(p1') [%p2] // x = inv(p1) [%(p2/d)] xy ans = gcdex(p1, p2); ll d = abs(p1 * ans.first + p2 * ans.second); ll mod = (p1 / d) * p2; if (((r2 - r1) % d) != 0) return xy{-1, 0}; ll s = (r2 - r1) / d; ll k = (s * ans.first) % (p2 / d); if (k < 0) k += p2 / d; xy pm = xy{k * p1 + r1, mod}; pm.first %= mod; if (pm.first < 0) pm.first += mod; subvec.push_back(pm); } if (n % 2) subvec.push_back(vec[n - 1]); return ganner(subvec); }; namespace zz_mod { template class pp { public: ll val; void flush() { val %= mod; if (val < 0) val += mod; }; void weak_flush() { if (val < 0) { val += mod; } else if (val >= mod) { val -= mod; } }; pp(ll x = 0) { val = x % mod; weak_flush(); }; friend std::ostream& operator<<(std::ostream& os, const pp& x) { return os << '{' << x.val << '|' << mod << '}'; }; pp& operator+=(const pp& p) { val += p.val; weak_flush(); return *this; }; pp& operator+=(ll x) { val += x % mod; weak_flush(); return *this; }; friend pp operator+(pp a, const pp& b) { return a += b; }; friend pp operator+(pp a, ll x) { return a += x; }; friend pp operator+(ll x, pp a) { return a += x; }; pp& operator-=(const pp& p) { val -= p.val; weak_flush(); return *this; }; pp& operator-=(ll x) { val -= x % mod; weak_flush(); return *this; }; friend pp operator-(pp a, const pp& b) { return a -= b; }; friend pp operator-(pp a, ll x) { return a -= x; }; friend pp operator-(ll x, const pp& a) { return pp(x) -= a; }; pp& operator*=(const pp& p) { val = (__int128)val * p.val; flush(); return *this; }; pp& operator*=(ll x) { val = (__int128)val * x; flush(); return *this; }; friend pp operator*(pp a, const pp& b) { return a *= b; }; friend pp operator*(pp a, ll x) { return a *= x; }; friend pp operator*(ll x, const pp& a) { return pp(x) *= a; }; pp inv() { xy ans = gcdex(mod, val); assert((mod * ans.first + val * ans.second) == 1); pp p(ans.second); return p; }; pp& operator/=(const pp& p) { return *this *= p.inv(); } pp& operator/=(ll x) { return *this *= gcdex(mod, x).second; } friend pp operator/(pp a, const pp& b) { return a /= b; }; friend pp operator/(pp a, ll x) { return a /= x; }; friend pp operator/(ll x, const pp& a) { a = a.inv(); return a /= x; }; pp exp(ll n) { if (n < 0) return inv().exp(-n); pp p = *this, ans(1); while (n > 1) { if (n & 1) ans *= p; p *= p; n >>= 1; } if (n > 0) ans *= p; return ans; }; }; } // namespace zz_mod using namespace zz_mod; ///////////////////////////////////////////////// namespace zz_poly { ll resize_2exp(vl& a) { ll nb = 0; while ((1 << nb) < a.size()) nb++; a.resize(1 << nb, 0); return nb; } template ll getFFTroot(ll len, bool rvs = false) { pp w; switch (mod) { case 880803841: // w = pp(26).exp(105).val; w = pp(26); break; case 897581057: // w = pp(3).exp(107).val; w = pp(3); break; case 998244353: // w = pp(3).exp(119).val; w = pp(3); break; default: assert("convolution nomatch mod" == ""); } if (rvs) return w.inv().exp((mod - 1) / len).val; return w.exp((mod - 1) / len).val; } template vl tran(const vl& vec, ll zeta) { ll n = vec.size(); if (n == 1) return vec; vl subvec1, subvec2; rep(i, n / 2) { subvec1.push_back(vec[2 * i]); subvec2.push_back(vec[2 * i + 1]); } vl SUBVEC1 = tran(subvec1, (zeta * zeta) % mod); vl SUBVEC2 = tran(subvec2, (zeta * zeta) % mod); ll w = 1; vl ans(n); rep(i, n) { ans[i] = (SUBVEC1[i % (n / 2)] + SUBVEC2[i % (n / 2)] * w) % mod; w = (w * zeta) % mod; } return ans; } template vl fft(vl& a) { resize_2exp(a); ll w = getFFTroot(a.size(), false); return tran(a, w); } template vl fft_reverse(vl& A) { resize_2exp(A); ll n = A.size(); ll w = getFFTroot(n, true); vl a = tran(A, w); rep(i, n) a[i] = (pp(a[i]) / n).val; return a; } template vl convolution(vl& a, vl& b) { ll n = a.size() + b.size() - 1; a.resize(n); b.resize(n); resize_2exp(a); resize_2exp(b); n = a.size(); // dbg::zout(getFFTroot(a.size(), false), pp(getFFTroot(a.size(), false)).exp(a.size()), // pp(getFFTroot(a.size(), false)).exp(a.size() / 2)); // dbg::zout(getFFTroot(a.size(), true), pp(getFFTroot(a.size(), true)).exp(a.size()), // pp(getFFTroot(a.size(), true)).exp(a.size() / 2)); dbg::zout("convolution a =", a); dbg::zout("convolution b =", b); vl A = fft(a); vl B = fft(b); dbg::zout("convolution A=", A); dbg::zout("convolution B=", B); vl C(n); rep(i, n) C[i] = pp(A[i] * B[i]).val; dbg::zout("convolution C=", C); vl c = fft_reverse(C); dbg::zout("convolution c =", c); return c; } }; // namespace zz_poly using namespace zz_poly; ///////////////////////////////////////////////// xy Gn(const vxy& vec, ll mod = -1) { ll n = vec.size(); if (n == 0) return xy{-1, mod}; if (mod == -1) { mod = lcm([&vec]() { vl v; each(ite, vec) v.push_back(ite->second); return v; }()); } // // x * p1 + y * p2 = d // (x*p1/d) = 1 [%(p2/d)] // (y*p2/d) = 1 [%(p1/d)] // r3 = r1 * (y*p2/d) + r2 * (x*p1/d) // p3 = lcm(p1,p2) dbg::zout("Gn: mod=", mod, " vec=", vec); ll r1 = 0, p1 = 1; rep(i, n) { xy prevrp = xy{r1, p1}; ll r2 = vec[i].first, p2 = vec[i].second; dbg::zout("Gn: rp1=", xy{r1, p1}, " rp2=", xy{r2, p2}); xy ans = gcdex(p1, p2); ll d = (ans.first * p1 + ans.second * p2); dbg::zout("Gn: ans=", ans, " d=", d); if (abs(r1 - r2) % d != 0) return xy{-1, mod}; ll a = ans.second * (p2 / d), b = ans.first * (p1 / d); dbg::zout("Gn: a=", a, " b=", b); p1 = p1 * (p2 / d); // a %= p1; // if (a < 0) a += p1; // b %= p1; // if (b < 0) b += p1; dbg::zout("Gn: a=", a, " b=", b); dbg::zout("Gn: r1*a=", (__int128)r1 * a, " r2*b=", (__int128)r2 * b); __int128 r3 = (__int128)r1 * a + (__int128)r2 * b; r3 %= p1; if (r3 < 0) r3 += p1; r1 = r3; // ll r3 = r1 * a; // r3 %= p1; // if (r3 < 0) r3 += p1; // r1 = (r2 * b); // r1 %= p1; // if (r1 < 0) r1 += p1; // r1 += r3; // if (r1 >= p1) r1 -= p1; dbg::zout("Gn: rp=", xy{r1, p1}); dbg::zout("Gm :[*]=", xy{r1 % prevrp.second, prevrp.first}); rcnt(j, i, 0) dbg::zout("Gm :[", j, "]=", xy{r1 % vec[j].second, vec[j].first}); } return xy{r1, p1}; } int main() { // dbg::unprint = true; vl x(3), y(3); rep(i, 3) cin >> x[i] >> y[i]; cout << Gn(vxy{xy{x[0], y[0]}, xy{x[1], y[1]}, xy{x[2], y[2]}}).first << endl; // ll N, M; // cin >> N >> M; // vl a(N), b(M); // rep(i, N) cin >> a[i]; // rep(i, M) cin >> b[i]; // vl a1 = a, b1 = b; // vl a2 = a, b2 = b; // vl a3 = a, b3 = b; // // vl c = convolution<998244353>(a1, b1); // vl c2 = convolution<880803841>(a2, b2); // vl c3 = convolution<897581057>(a3, b3); // rep(i, N + M - 1) { cout << ganner(vxy{xy{c2[i], 880803841}, xy{c3[i], 897581057}}).first % 1000000007 << " "; } // cout << endl; return 0; }