import java.util.HashMap;

public class Euler809 {

    static long powMod(long a, long e, long mod) {
        if (mod == 1)
            return 0;
        long r = 1 % mod;
        a %= mod;
        while (e > 0) {
            if ((e & 1L) == 1L) {
                r = java.math.BigInteger.valueOf(r).multiply(java.math.BigInteger.valueOf(a))
                        .mod(java.math.BigInteger.valueOf(mod)).longValue();
            }
            a = java.math.BigInteger.valueOf(a).multiply(java.math.BigInteger.valueOf(a))
                    .mod(java.math.BigInteger.valueOf(mod)).longValue();
            e >>= 1L;
        }
        return r;
    }

    static long invMod(long a, long mod) {
        long t = 0, nt = 1;
        long r = mod, nr = a % mod;
        while (nr != 0) {
            long q = r / nr;
            long tt = t - q * nt;
            t = nt;
            nt = tt;
            long rr = r - q * nr;
            r = nr;
            nr = rr;
        }
        if (t < 0)
            t += mod;
        return t;
    }

    static long powModSigned2(long exp, long mod) {
        if (mod == 1)
            return 0;
        if (exp >= 0)
            return powMod(2, exp, mod);
        long inv2 = invMod(2, mod);
        return powMod(inv2, -exp, mod);
    }

    static long phi(long n) {
        if (n == 0)
            return 0;
        long result = n;
        if ((n & 1L) == 0L) {
            result -= result / 2;
            while ((n & 1L) == 0L) {
                n >>= 1L;
            }
        }
        for (long p = 3; p * p <= n; p += 2) {
            if (n % p != 0)
                continue;
            result -= result / p;
            while (n % p == 0) {
                n /= p;
            }
        }
        if (n > 1) {
            result -= result / n;
        }
        return result;
    }

    static HashMap<Long, Long> memo = new HashMap<>();

    static long tower2FixpointMod(long mod) {
        Long cached = memo.get(mod);
        if (cached != null)
            return cached;

        long odd = mod;
        long twos = 0;
        while ((odd & 1L) == 0L) {
            odd >>= 1L;
            twos++;
        }

        long t = phi(odd);
        long w = (t == 1) ? 0 : tower2FixpointMod(t) - twos;
        long oddPart = powModSigned2(w, odd);
        long ans = (oddPart << twos) % mod;
        memo.put(mod, ans);
        return ans;
    }

    public static String solve() {
        memo.put(1L, 0L);
        long MOD = 1000000000000000L;
        long top = tower2FixpointMod(MOD);
        return Long.toString((top + MOD - 3) % MOD);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}