#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e8 + 10;
const LL n = 1001733993063167141ll;
const LL p = 891234941ll;
const LL q = 1123984201ll;
const LL d = 212353;
const LL c = 20190324;
int a[maxn];
int sushu[maxn / 10];
bool notPrime[maxn]; ///筛素数分解不出来，目测是9位数*10位数
int cnt;
void getPrime(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!notPrime[i])
            sushu[cnt++] = i;
        for (int j = 0; j < cnt && 1ll * i * sushu[j] <= n; ++j)
        {
            notPrime[i * sushu[j]] = true;
            if (i % sushu[j] == 0)
                break;
        }
    }
    for (int i = 0; i < 20; ++i)
        cout << sushu[i] << " ";
    cout << endl;
}
void fenjie(LL x)
{
    cout << x << " = 1";
    for (int i = 0; i < cnt && sushu[i] <= x / sushu[i]; ++i)
    {
        while (x % sushu[i] == 0)
        {
            cout << " * " << sushu[i];
            x /= sushu[i];
        }
    }
    if (x > 1)
        cout << " * " << x;
    cout << endl;
}
void BF(LL x)
{
    cout << x << " = ";
    for (LL i = 1e8 + 1; i < x; i += 2)
    {
        if (x % i == 0)
            cout << i << " * ", x /= i;
    }
    cout << x << endl;
}
void exgcd(LL a, LL b, LL &d, LL &x, LL &y)
{
    if (b == 0)
    {
        d = a;
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, d, y, x);
    y -= (a / b) * x;
}
LL rev(LL t, LL m)
{
    LL d, x, y;
    exgcd(t, m, d, x, y);
    return (x % m + m) % m;
}
LL fast_product(LL a, LL b, LL mod)
{
    LL ans = 0;
    while (b)
    {
        if (b & 1)
            ans = (ans + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans;
}
LL fast_pow(LL a, LL b, LL mod)
{
    LL ans = 1;
    while (b)
    {
        if (b & 1)
            ans = fast_product(ans, a, mod);
        a = fast_product(a, a, mod);
        b >>= 1;
    }
    return ans;
}
int main()
{
    //getPrime(maxn-5);
    //fenjie(n);
    BF(n);
    LL y = (p - 1) * (q - 1);
    LL e = rev(d, y);
    LL answer = fast_pow(c, e, n);
    cout << answer << endl;

    return 0;
}