import java.util.ArrayList;

public class Euler839 {

    static class Block {
        long sum;
        int len;

        Block(long sum, int len) {
            this.sum = sum;
            this.len = len;
        }
    }

    static java.math.BigInteger toBI(long v) {
        return java.math.BigInteger.valueOf(v);
    }

    static String computeB(int n) {
        final long kMod = 50515093L;
        ArrayList<Block> st = new ArrayList<>(1000000);

        long s = 290797L;
        java.math.BigInteger prefInit = java.math.BigInteger.ZERO;
        java.math.BigInteger sumPrefInit = java.math.BigInteger.ZERO;

        for (int i = 0; i < n; ++i) {
            long v = s;
            prefInit = prefInit.add(toBI(v));
            sumPrefInit = sumPrefInit.add(prefInit);

            s = (s * s) % kMod;

            st.add(new Block(v, 1));
            while (st.size() >= 2) {
                Block right = st.get(st.size() - 1);
                Block left = st.get(st.size() - 2);
                long leftMax = (left.sum + left.len - 1) / left.len;
                long rightMin = right.sum / right.len;
                if (leftMax <= rightMin)
                    break;
                left.sum += right.sum;
                left.len += right.len;
                st.remove(st.size() - 1);
            }
        }

        java.math.BigInteger prefFinal = java.math.BigInteger.ZERO;
        java.math.BigInteger sumPrefFinal = java.math.BigInteger.ZERO;

        for (Block b : st) {
            long len = b.len;
            long q = b.sum / len;
            long r = b.sum % len;

            long cntQ = len - r;
            if (cntQ > 0) {
                sumPrefFinal = sumPrefFinal.add(toBI(cntQ).multiply(prefFinal));
                java.math.BigInteger term2 = toBI(q).multiply(toBI(cntQ)).multiply(toBI(cntQ + 1)).divide(toBI(2));
                sumPrefFinal = sumPrefFinal.add(term2);
                prefFinal = prefFinal.add(toBI(cntQ * q));
            }

            long cntQ1 = r;
            if (cntQ1 > 0) {
                long qp1 = q + 1;
                sumPrefFinal = sumPrefFinal.add(toBI(cntQ1).multiply(prefFinal));
                java.math.BigInteger term2 = toBI(qp1).multiply(toBI(cntQ1)).multiply(toBI(cntQ1 + 1)).divide(toBI(2));
                sumPrefFinal = sumPrefFinal.add(term2);
                prefFinal = prefFinal.add(toBI(cntQ1 * qp1));
            }
        }

        return sumPrefInit.subtract(sumPrefFinal).toString();
    }

    public static String solve() {
        return computeB(10000000);
    }

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