import java.util.Arrays;

public class Euler793 {

    static final long MOD = 50515093L;

    static long[] buildValues(int n) {
        long[] a = new long[n];
        long s = 290797L;
        for (int i = 0; i < n; i++) {
            a[i] = s;
            s = (s * s) % MOD;
        }
        Arrays.sort(a);
        return a;
    }

    static long countPairsLeq(long[] a, long x) {
        int n = a.length;
        int j = n - 1;
        long cnt = 0;

        for (int i = 0; i < n; i++) {
            while (i < j && a[i] * a[j] > x) {
                j--;
            }
            if (j <= i) {
                break;
            }
            cnt += (j - i);
        }

        return cnt;
    }

    static long solveN(int n) {
        long[] a = buildValues(n);

        long m = (long) n * (n - 1) / 2L;
        long target = (m + 1L) / 2L;

        long lo = 0;
        long hi = a[n - 1] * a[n - 2];

        while (lo < hi) {
            long mid = lo + (hi - lo) / 2L;
            if (countPairsLeq(a, mid) >= target) {
                hi = mid;
            } else {
                lo = mid + 1L;
            }
        }

        return lo;
    }

    public static String solve() {
        return Long.toString(solveN(1000003));
    }

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