#ifndef rtgsp
#include "Alice.h"
#endif // rtgsp
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 4;
#ifdef rtgsp
ll setn (int n)
{
ll x;
cin >> x;
return x;
}
#endif // rtgsp
int n;
vector<pair<int, int>> Alice()
{
n = 5000;
ll x = setn(n);
vector<pair<int, int>> v;
v.clear();
for (int i = 2; i <= n; i++)
v.push_back({x % (i - 1) + 1, i});
return v;
}
#ifdef rtgsp
int main ()
{
freopen(task".OUT", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<pair<int, int>> v = Alice();
for (pair<int, int> p : v) cout << p.first << " " << p.second << '\n';
}
#endif // rtgsp
#ifndef rtgsp
#include "Bob.h"
#endif // rtgsp
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 4;
int min_prime[maxn], primes[maxn], mod[maxn], cnt = 0;
void sieve()
{
for (int i = 2; i < maxn; i++)
{
if (min_prime[i] == 0)
{
min_prime[i] = i;
primes[++cnt] = i;
mod[i] = -1;
}
for (int j = 1; i * primes[j] < maxn; j++)
{
min_prime[i * primes[j]] = primes[j];
if (min_prime[i] == primes[j]) break;
}
}
}
ll inv_mod (__int128 x, int mod)
{
int p = mod - 2;
x %= mod;
ll res = 1;
for (; p > 0; p >>= 1)
{
if (p & 1) res = res * x % mod;
x = x * x % mod;
}
return res;
}
void print (__int128 x)
{
string s;
while (x != 0)
{
s.push_back((x % 10) + '0');
x /= 10;
}
reverse(s.begin(), s.end());
cout << s;
}
ll Bob(vector<pair<int, int>> v)
{
ll mx = 0, ans = 0;
__int128 res = 0, cur = 1;
sieve();
for (pair<int, int> p : v)
{
p.first--; p.second--;
while (p.second != 1)
{
mod[min_prime[p.second]] = p.first % min_prime[p.second];
p.second /= min_prime[p.second];
}
}
for (int i = 1; i <= cnt; i++)
{
if (mod[primes[i]] == -1) continue;
if (cur > 1e18)
{
mx = i - 1;
break;
}
else cur *= primes[i];
}
for (int i = 1; i <= mx; i++)
{
if (mod[primes[i]] == -1) continue;
__int128 mi = cur/primes[i];
ll ni = inv_mod(mi, primes[i]);
res = (res + mod[primes[i]]*mi%cur*ni%cur)%cur;
}
ans = res;
return ans;
}
#ifdef rtgsp
int main ()
{
freopen(task".OUT", "r", stdin);
ios_base::sync_with_stdio(0);
cin.tie(0);
int n = 5000, x, y;
vector<pair<int, int>> v;
v.clear();
for (int i = 1; i <= (n - 2)/2; i++)
{
cin >> x >> y;
v.push_back({x, y});
}
cout << Bob(v);
}
#endif // rtgsp
