import java.util.ArrayList;
import java.util.List;

public class Euler375 {
    static final long kMod = 50515093L;
    static final long kTargetN = 2000000000L;

    static List<Integer> buildPeriodSequence() {
        long s = 290797L;
        s = (s * s) % kMod;
        int first = (int) s;

        List<Integer> seq = new ArrayList<>(6500000);
        while (true) {
            seq.add((int) s);
            s = (s * s) % kMod;
            if ((int) s == first) {
                break;
            }
        }
        return seq;
    }

    static int valueAt(List<Integer> a, int pos) {
        int p = a.size();
        return a.get((pos - 1) % p);
    }

    static void buildSpans(List<Integer> a, int[] dLeft, int[] dRight) {
        int p = a.size();
        int[] stack = new int[2 * p + 8];
        int top = 0;

        for (int pos = 2 * p; pos >= 1; pos--) {
            int v = valueAt(a, pos);
            while (top > 0 && valueAt(a, stack[top - 1]) > v) {
                top--;
            }
            if (pos <= p) {
                dRight[pos - 1] = top > 0 ? (stack[top - 1] - pos) : 0;
            }
            stack[top++] = pos;
            if (pos == 1)
                break;
        }

        top = 0;
        for (int pos = 1; pos <= 2 * p; pos++) {
            int v = valueAt(a, pos);
            while (top > 0 && valueAt(a, stack[top - 1]) >= v) {
                top--;
            }
            if (pos > p) {
                int idx = pos - p;
                if (top > 0 && stack[top - 1] >= idx) {
                    dLeft[idx - 1] = pos - stack[top - 1];
                } else {
                    dLeft[idx - 1] = 0;
                }
            }
            stack[top++] = pos;
        }
    }

    static long sumSubarrayMinPrefix(List<Integer> a, int[] dLeft, int[] dRight, long n) {
        long p = a.size();
        long q = n / p;
        long r = n % p;

        long total = 0;
        for (long idx = 1; idx <= p; idx++) {
            long occ = q + ((idx <= r) ? 1 : 0);
            if (occ == 0)
                continue;

            long v = a.get((int) (idx - 1));
            long dr = dRight[(int) (idx - 1)];
            long dl = dLeft[(int) (idx - 1)];

            long remLast = (idx <= r) ? (r - idx + 1) : (p + r - idx + 1);
            long rLast = Math.min(dr, remLast);

            if (dl == 0) {
                if (occ == 1) {
                    total += v * idx * rLast;
                } else {
                    long n1 = occ - 1;
                    long sumL = n1 * idx + p * (n1 - 1) * n1 / 2;
                    total += v * dr * sumL;

                    long lLast = (occ - 1) * p + idx;
                    total += v * lLast * rLast;
                }
            } else {
                if (occ == 1) {
                    long l0 = Math.min(dl, idx);
                    total += v * l0 * rLast;
                } else {
                    long l0 = Math.min(dl, idx);
                    total += v * l0 * dr;
                    if (occ > 2) {
                        total += v * dl * dr * (occ - 2);
                    }
                    total += v * dl * rLast;
                }
            }
        }
        return total;
    }

    static String solve() {
        List<Integer> period = buildPeriodSequence();
        int p = period.size();
        int[] dLeft = new int[p];
        int[] dRight = new int[p];
        buildSpans(period, dLeft, dRight);

        long answer = sumSubarrayMinPrefix(period, dLeft, dRight, kTargetN);
        return Long.toString(answer); // Works for BigInteger since it fits in Long
    }

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