#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 1e6 + 10;
typedef pair<int, int> pii;

__int128 p, mod;

inline __int128 read()
{
    __int128 x = 0, y = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') y = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * y;
}

inline void write(__int128 x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

__int128 exgcd(__int128 a,__int128 b,__int128 &x,__int128 &y)
{
   // return b?gcd(b,a%b):a;
   //展开写
   if(!b)//当b为0时，a和0的最大公约数为a，a*x+*y=a,x=1，y=0
   {
       x=1,y=0;
       return a;
   }
   __int128 d= exgcd(b,a%b,y,x);//记下最大公约数 ,b都系数为y，a%b的系数为x
   //递归结束后，此时已有一组x，y，使得by+(a%b)x=d
   y-=a/b*x;
   return d;
}

__int128 qmi(__int128 a, __int128 k) {
    __int128 res = 1;
    while (k) {
        if (k & 1) res = res * a;
        k >>= 1;
        a = a * a;
    }
    return res;
}

void solve()
{
    mod = qmi(2, 64);
    p = read();
    __int128 x, y;
    exgcd(p, mod, x, y);
    x = (x + mod) % mod;
    write(x);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    // cin >> _;
    while (_ -- )
    {
        solve();
    }
    return 0;
}