import java.util.Arrays;

public class Euler653 {
    static final long kRMod = 32745673L;
    static final long kRSeed = 6563116L;
    static final long kThreshold = 10000000L;

    static long solveCase(long L, int N, int j) {
        long r = kRSeed;
        long cumulativeGap = 0;
        long boundary = L - 10 - 20L * (j - 1);

        long[] times = new long[N];

        for (int idx = 0; idx < N; ++idx) {
            long gap = (r % 1000) + 1;
            cumulativeGap += gap;

            boolean eastward = (r <= kThreshold);
            long t = eastward ? (boundary - cumulativeGap) : (boundary + cumulativeGap);
            times[idx] = t;

            r = (r * r) % kRMod;
        }

        int kth = N - j;
        Arrays.sort(times);
        return times[kth];
    }

    public static String solve() {
        long ans = solveCase(1000000000L, 1000001, 500001);
        return Long.toString(ans);
    }

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