public class Euler426 {
    private static final int TARGET_INDEX = 10000000;
    private static final long SEED = 290797L;
    private static final long MOD = 50515093L;

    public static String solve() {
        int[] stack = new int[TARGET_INDEX + 100];
        int stackSize = 0;

        long[] roundCounts = new long[TARGET_INDEX / 2 + 100];
        int maxRound = 0;

        long s = SEED;
        boolean occupied = true;

        for (int i = 0; i <= TARGET_INDEX; i++) {
            int runLength = (int) (s % 64) + 1;

            if (occupied) {
                while (stackSize + runLength > stack.length) {
                    int[] newStack = new int[stack.length * 2];
                    System.arraycopy(stack, 0, newStack, 0, stackSize);
                    stack = newStack;
                }
                for (int j = 0; j < runLength; j++) {
                    stack[stackSize++] = 0;
                }
            } else {
                int rl = runLength;
                while (rl > 0 && stackSize > 0) {
                    int childMaxRound = stack[--stackSize];
                    int rnd = childMaxRound + 1;

                    if (rnd > maxRound) {
                        maxRound = rnd;
                        if (maxRound >= roundCounts.length) {
                            long[] newCounts = new long[Math.max(roundCounts.length * 2, maxRound + 100)];
                            System.arraycopy(roundCounts, 0, newCounts, 0, roundCounts.length);
                            roundCounts = newCounts;
                        }
                    }
                    roundCounts[rnd]++;

                    if (stackSize > 0 && stack[stackSize - 1] < rnd) {
                        stack[stackSize - 1] = rnd;
                    }
                    rl--;
                }
            }

            occupied = !occupied;
            s = (s * s) % MOD;
        }

        while (stackSize > 0) {
            int childMaxRound = stack[--stackSize];
            int rnd = childMaxRound + 1;

            if (rnd > maxRound) {
                maxRound = rnd;
                if (maxRound >= roundCounts.length) {
                    long[] newCounts = new long[Math.max(roundCounts.length * 2, maxRound + 100)];
                    System.arraycopy(roundCounts, 0, newCounts, 0, roundCounts.length);
                    roundCounts = newCounts;
                }
            }
            roundCounts[rnd]++;

            if (stackSize > 0 && stack[stackSize - 1] < rnd) {
                stack[stackSize - 1] = rnd;
            }
        }

        long ans = 0;
        for (int rnd = 1; rnd <= maxRound; rnd++) {
            ans += (2L * rnd - 1) * roundCounts[rnd];
        }

        return String.valueOf(ans);
    }

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