import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Euler477 {

    private static final long kMod = 1_000_000_007L;

    private static long nextValue(long x) {
        return (x * x + 45L) % kMod;
    }

    private static long computeScore(List<Integer> seq) {
        long[] stack = new long[seq.size() + 10];
        int top = 0;

        long sum = 0;
        for (int v : seq) {
            sum += v;
            stack[top++] = v;
            while (top >= 3) {
                long a = stack[top - 3];
                long b = stack[top - 2];
                long c = stack[top - 1];
                if (b < a || b < c) {
                    break;
                }
                stack[top - 3] = a - b + c;
                top -= 2;
            }
        }

        long delta = 0;
        int i = 0;
        int j = top - 1;
        long sign = 1;

        while (top > 0 && i <= j) {
            if (stack[i] > stack[j]) {
                delta += sign * stack[i];
                i++;
            } else {
                delta += sign * stack[j];
                if (j == 0)
                    break;
                j--;
            }
            sign = -sign;
        }

        return (sum + delta) / 2;
    }

    private static long solveN(long n) {
        if (n == 0)
            return 0;

        Map<Integer, Integer> seen = new HashMap<>(100000);
        List<Integer> prefix = new ArrayList<>(100000);

        int s = 0;
        int cycleStart = -1;
        int cycleLen = 0;

        for (long i = 0; i < n; ++i) {
            if (seen.containsKey(s)) {
                cycleStart = seen.get(s);
                cycleLen = prefix.size() - cycleStart;
                break;
            }
            seen.put(s, prefix.size());
            prefix.add(s);
            s = (int) nextValue(s);
        }

        if (cycleStart < 0) {
            return computeScore(prefix);
        }

        long p = cycleStart;
        long cycle = cycleLen;

        long a = (n - p) % cycle;
        long b = cycle - a;

        List<Integer> U = new ArrayList<>();
        U.addAll(prefix.subList(0, (int) p));
        U.addAll(prefix.subList((int) p, (int) (p + a)));

        List<Integer> V = new ArrayList<>();
        V.addAll(prefix.subList((int) (p + a), (int) (p + a + b)));
        V.addAll(prefix.subList((int) p, (int) (p + a)));

        List<Integer> T = new ArrayList<>();
        T.addAll(U);
        T.addAll(V);

        long s1 = computeScore(U);
        long s2 = computeScore(T);

        long uLen = U.size();
        long vLen = V.size();
        long blocks = (n - uLen) / vLen;

        return s1 + (s2 - s1) * blocks;
    }

    public static void main(String[] args) {
        long n = 100_000_000L;
        System.out.println(solveN(n));
    }
}