#include "Alice.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>
#define pb push_back
#define eb emplace_back
#define emp emplace
#define mkp make_pair
#define mkt make_tuple
#define vctr vector
#define arr array
#define all(x) x.begin(), x.end()
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)
#define brick(x) cout << #x << " = " << (x) << " | "
#define dbg(x) cout << #x << " = " << (x) << '\n'
#define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n'
#define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n'
#define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n'
mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));
int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }
const int MOD = 1e9+7; // 998244353;
int n;
ll setN(int _n) {
n = _n;
ll x;
cin >> x;
return x;
}
vctr<pii> Alice() {
ll x = setN(5000);
--x;
vctr<pii> res;
for (int i = 2; i <= 5000; ++i) {
res.eb((x%(i-1))+1,i);
}
return res;
}
// int main() {
// vctr<pii> res = Alice();
// shuffle(all(res),rng);
// res.resize(res.size()-(n-2)/2);
// sort(all(res));
// cout << res.size() << '\n';
// for (auto it : res) {
// cout << it.f << ' ' << it.s << '\n';
// }
// }
// #include "Bob.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>
#define pb push_back
#define eb emplace_back
#define emp emplace
#define mkp make_pair
#define mkt make_tuple
#define vctr vector
#define arr array
#define all(x) x.begin(), x.end()
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)
#define brick(x) cout << #x << " = " << (x) << " | "
#define dbg(x) cout << #x << " = " << (x) << '\n'
#define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n'
#define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n'
#define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n'
mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));
int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }
const int MOD = 1e9+7; // 998244353;
pair<__int128,__int128> euclid(__int128 a, __int128 b) {
__int128 x = 1, y = 0, x1 = 0, y1 = 1;
while (b) {
__int128 q = a/b;
tie(a,b) = mkp(b,a-q*b);
tie(x,x1) = mkp(x1,x-q*x1);
tie(y,y1) = mkp(y1,y-q*y1);
}
return mkp(a,x);
}
ll Bob(vctr<pii> v){
// add your code here
/*
x = a mod n
y = b mod m
x = (kn+a)
g = gcd(n,m)
kn+a = b mod m
kn = b-a mod m
if ((b-a)%g != 0)no result
k(n/g) = (b-a)/g mod m/g
x(n/g)+y(m/g) = 1
k = (b-a)/g * x mod m/g
k = c mod (m/g)
k = l(m/g)+c
x = (l(m/g)+c)n+a
x = l(lcm(n,m))+cn+a
x = cn+a mod lcm(n,m)
*/
__int128 a = 0, n = 1;
for (auto [x,y] : v) {
__int128 b = x-1;
__int128 m = y-1;
// brick((ll)b);dbg((ll)m);
pair<__int128,__int128> g = euclid(n,m);
__int128 pn = n;
n /= g.f;
m /= g.f;
// brick((ll)n);dbg((ll)m);
// dbg((ll)g.s);
__int128 c = (b-a)/g.f;
c *= g.s;
// dbg((ll)c);
a = c*pn+a;
n = pn*m;
a = (a%n+n)%n;
if (n >= (__int128)1e18)break;
// brick((ll)a);dbg((ll)n);
}
return a+1;
}
// int main() {
// int m;
// cin >> m;
// vctr<pii> res;
// for (int i = 1; i <= m; ++i) {
// int u, v;
// cin >> u >> v;
// res.eb(u,v);
// }
// cout << Bob(res) << '\n';
// }
