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

public class Euler917 {

    static final long MOD = 998388889L;
    static final long SEED = 102022661L;

    static class ABData {
        int[] a;
        int[] b;
        long sumA;
        long sumB;
    }

    static ABData generateAb(int n) {
        ABData data = new ABData();
        data.a = new int[n + 1];
        data.b = new int[n + 1];
        data.sumA = 0;
        data.sumB = 0;

        long s = SEED;
        for (int i = 1; i <= n; ++i) {
            data.a[i] = (int) s;
            data.sumA += s;

            s = (s * s) % MOD;
            data.b[i] = (int) s;
            data.sumB += s;

            if (i != n) {
                s = (s * s) % MOD;
            }
        }
        return data;
    }

    static BigInteger cross(int t1, int t2, int t3, int[] b) {
        long x1 = t2 - t1;
        long y1 = (long) b[t2 + 1] - (long) b[t1 + 1];
        long x2 = t3 - t1;
        long y2 = (long) b[t3 + 1] - (long) b[t1 + 1];

        BigInteger bx1 = BigInteger.valueOf(x1);
        BigInteger by1 = BigInteger.valueOf(y1);
        BigInteger bx2 = BigInteger.valueOf(x2);
        BigInteger by2 = BigInteger.valueOf(y2);

        return bx1.multiply(by2).subtract(by1.multiply(bx2));
    }

    static List<Integer> lowerHullIndices(int[] b, int maxT) {
        List<Integer> hull = new ArrayList<>();

        for (int t = 0; t <= maxT; ++t) {
            while (hull.size() >= 2) {
                int t1 = hull.get(hull.size() - 2);
                int t2 = hull.get(hull.size() - 1);
                if (cross(t1, t2, t, b).compareTo(BigInteger.ZERO) <= 0) {
                    hull.remove(hull.size() - 1);
                } else {
                    break;
                }
            }
            hull.add(t);
        }
        return hull;
    }

    static long minimalExtraCost(int[] a, int[] b, int n) {
        int edgeSteps = n - 1;
        if (edgeSteps == 0)
            return 0;

        List<Integer> hullT = lowerHullIndices(b, edgeSteps);
        int m = hullT.size();

        long[] tVals = new long[m];
        long[] gVals = new long[m];
        for (int k = 0; k < m; ++k) {
            tVals[k] = hullT.get(k);
            gVals[k] = b[hullT.get(k) + 1];
        }

        long[] prev = new long[m];
        long[] cur = new long[m];

        for (int i = 1; i <= edgeSteps; ++i) {
            long u = (long) a[i] - (long) a[i + 1];
            long pref = Long.MAX_VALUE;
            for (int k = 0; k < m; ++k) {
                if (prev[k] < pref) {
                    pref = prev[k];
                }
                cur[k] = pref + u * tVals[k] + gVals[k];
            }
            long[] temp = prev;
            prev = cur;
            cur = temp;
        }

        long best = prev[0];
        for (int k = 1; k < m; ++k) {
            if (prev[k] < best) {
                best = prev[k];
            }
        }

        return (long) edgeSteps * (long) a[n] + best;
    }

    static long solveFast(int n) {
        ABData data = generateAb(n);
        long extra = minimalExtraCost(data.a, data.b, n);
        return data.sumA + data.sumB + extra;
    }

    public static String solve() {
        return Long.toString(solveFast(10000000));
    }

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