import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Euler541 {

    static long mulMod(long a, long b, long mod) {
        if (a == 0 || b == 0)
            return 0;
        return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b)).mod(BigInteger.valueOf(mod)).longValue();
    }

    static long subMod(long a, long b, long mod) {
        long res = a - b;
        if (res < 0)
            res += mod;
        return res;
    }

    static long modInv(long a, long mod) {
        long origMod = mod;
        a %= mod;
        long x = 0, y = 1, lastx = 1, lasty = 0, temp;
        long b = mod;
        while (b != 0) {
            long q = a / b;
            long r = a % b;
            a = b;
            b = r;
            temp = x;
            x = lastx - q * x;
            lastx = temp;
            temp = y;
            y = lasty - q * y;
            lasty = temp;
        }
        long res = lastx % origMod;
        if (res < 0)
            res += origMod;
        return res;
    }

    static long powMod(long a, long e, long mod) {
        long res = 1 % mod;
        a %= mod;
        while (e > 0) {
            if ((e & 1) != 0)
                res = mulMod(res, a, mod);
            a = mulMod(a, a, mod);
            e >>= 1;
        }
        return res;
    }

    static boolean isPrimeTrial(long p) {
        if (p < 2)
            return false;
        if (p % 2 == 0)
            return p == 2;
        for (long d = 3; d * d <= p; d += 2) {
            if (p % d == 0)
                return false;
        }
        return true;
    }

    static long[] powTable(long p, int S) {
        long[] pp = new long[S + 1];
        pp[0] = 1;
        for (int i = 1; i <= S; i++)
            pp[i] = pp[i - 1] * p;
        return pp;
    }

    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    static long[] computeCoeffC(long p, int S) {
        long[] pPow = powTable(p, S);
        long mod = pPow[S];
        int N = (S - 1) / 2;
        if (N <= 0)
            return new long[0];

        List<Long> sampleN = new ArrayList<>();
        long n_val = 1;
        while (sampleN.size() < N) {
            if (n_val % p != 0)
                sampleN.add(n_val);
            n_val++;
        }

        long[] b = new long[N];
        for (int i = 0; i < N; i++) {
            long n = sampleN.get(i);
            long sum = 0;
            long up = p * n;
            for (long m = 1; m <= up; m++) {
                if (m % p == 0)
                    continue;
                sum += modInv(m, mod);
                if (sum >= mod)
                    sum %= mod;
            }
            b[i] = sum % mod;
        }

        long[][] M = new long[N][N + 1];
        for (int i = 0; i < N; i++) {
            long n = sampleN.get(i);
            for (int k = 0; k < N; k++) {
                M[i][k] = powMod(n, 2 * (k + 1), mod);
            }
            M[i][N] = b[i];
        }

        for (int col = 0; col < N; col++) {
            int pivot = -1;
            for (int r = col; r < N; r++) {
                if (gcd(M[r][col], mod) == 1) {
                    pivot = r;
                    break;
                }
            }
            if (pivot == -1)
                throw new RuntimeException("Coefficient solve failed");
            if (pivot != col) {
                long[] temp = M[pivot];
                M[pivot] = M[col];
                M[col] = temp;
            }

            long invPivot = modInv(M[col][col], mod);
            for (int c = col; c <= N; c++) {
                M[col][c] = mulMod(M[col][c], invPivot, mod);
            }

            for (int r = 0; r < N; r++) {
                if (r == col)
                    continue;
                long factor = M[r][col];
                if (factor == 0)
                    continue;
                for (int c = col; c <= N; c++) {
                    long sub = mulMod(factor, M[col][c], mod);
                    M[r][c] = subMod(M[r][c], sub, mod);
                }
            }
        }

        long[] C = new long[N];
        for (int i = 0; i < N; i++)
            C[i] = M[i][N] % mod;

        return C;
    }

    static class Node {
        long n;
        long H;

        Node(long n, long H) {
            this.n = n;
            this.H = H;
        }
    }

    static long maxJp(long p, int S) {
        if (p < 3 || p % 2 == 0)
            throw new RuntimeException("p must be odd prime");
        if (!isPrimeTrial(p))
            throw new RuntimeException("p is not prime");

        long[] pPow = powTable(p, S);
        long modS = pPow[S];
        long[] C = computeCoeffC(p, S);

        long[] Hsmall = new long[(int) p];
        Hsmall[0] = 0;
        for (int n = 1; n < p; n++) {
            Hsmall[n] = (Hsmall[n - 1] + modInv(n, modS)) % modS;
        }

        List<Node> cur = new ArrayList<>();
        long maxn = 0;
        for (int n = 1; n < p; n++) {
            if (Hsmall[n] % p == 0) {
                cur.add(new Node(n, Hsmall[n]));
                maxn = Math.max(maxn, n);
            }
        }

        int r = S;
        while (!cur.isEmpty() && r >= 2) {
            long mod_r = pPow[r];
            long mod_next = pPow[r - 1];

            List<Node> nxt = new ArrayList<>();
            for (Node node : cur) {
                long n = node.n;
                long hn = node.H % mod_r;
                long hn_div_p = (hn / p) % mod_next;

                long poly = 0;
                long nmod = n % mod_next;
                long n2 = mulMod(nmod, nmod, mod_next);
                long pow_n2k = n2;

                for (long ck_full : C) {
                    long ck = ck_full % mod_next;
                    if (ck != 0) {
                        poly = (poly + mulMod(ck, pow_n2k, mod_next)) % mod_next;
                    }
                    pow_n2k = mulMod(pow_n2k, n2, mod_next);
                }

                long hp_n = (hn_div_p + poly) % mod_next;

                if (hp_n % p == 0) {
                    nxt.add(new Node(p * n, hp_n));
                    maxn = Math.max(maxn, p * n);
                }

                long h = hp_n;
                for (long k = 1; k < p; k++) {
                    long denom = p * n + k;
                    long invd = modInv(denom, mod_next);
                    h = (h + invd) % mod_next;
                    if (h % p == 0) {
                        nxt.add(new Node(p * n + k, h));
                        maxn = Math.max(maxn, p * n + k);
                    }
                }
            }
            cur = nxt;
            r--;
        }

        if (!cur.isEmpty() && r < 2) {
            throw new RuntimeException("Precision S too low: increase S.");
        }

        return maxn;
    }

    static long computeM(long p, int S) {
        long maxJ = maxJp(p, S);
        return p * maxJ + (p - 1);
    }

    public static String solve() {
        return Long.toString(computeM(137, 8));
    }

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