public class Euler288 {
    static long powU64(long base, int exp) {
        long value = 1;
        for (int i = 0; i < exp; ++i) {
            value *= base;
        }
        return value;
    }

    public static String solve() {
        int p = 61;
        int q = 10000000;
        int exponent = 10;

        long mod = powU64(p, exponent);
        int firstLen = Math.min(exponent, q + 1);
        long[] prefix = new long[firstLen + 1];

        long s = 290797L;
        long total = 0L;
        for (int n = 0; n <= q; ++n) {
            long t = s % p;
            total += t;
            if (n < firstLen) {
                prefix[n + 1] = prefix[n] + t;
            }
            s = (s * s) % 50515093L;
        }

        long answer = 0L;
        long pPow = 1L;
        for (int j = 0; j < exponent; ++j) {
            long pref = 0L;
            if (j + 1 <= firstLen) {
                pref = prefix[j + 1];
            } else if (firstLen == q + 1) {
                pref = total;
            } else {
                pref = prefix[firstLen];
            }

            long suffix = total - pref;

            // answer = (answer + pPow * (suffix % mod)) % mod
            long term = (pPow % mod) * (suffix % mod); // pPow < mod, suffix%mod < mod. Could overflow long if mod is
                                                       // large.
            // But mod is 61^10 = 7.19 * 10^17.
            // We need u128 multiplication equivalent or BigInteger.
            // Using BigInteger to be safe.
            java.math.BigInteger bigTerm = java.math.BigInteger.valueOf(pPow)
                    .multiply(java.math.BigInteger.valueOf(suffix % mod));
            java.math.BigInteger bigAnswer = java.math.BigInteger.valueOf(answer)
                    .add(bigTerm).mod(java.math.BigInteger.valueOf(mod));
            answer = bigAnswer.longValue();

            pPow = java.math.BigInteger.valueOf(pPow)
                    .multiply(java.math.BigInteger.valueOf(p))
                    .mod(java.math.BigInteger.valueOf(mod)).longValue();
        }

        return String.valueOf(answer);
    }

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