import java.util.*;
import java.util.concurrent.*;

public class Euler238 {
    static final long MODULUS = 20300713;
    static final long SEED = 14025256;
    static final long LIMIT = 2000000000000000L;

    public static String solve() {
        List<Integer> wDigits = new ArrayList<>();
        List<Long> prefixSum = new ArrayList<>();
        Map<Long, Integer> seen = new HashMap<>();

        long s = SEED;
        int index = 0;

        while (!seen.containsKey(s)) {
            seen.put(s, index);
            String sStr = String.valueOf(s);
            for (int i = 0; i < sStr.length(); i++) {
                wDigits.add(sStr.charAt(i) - '0');
            }
            s = (s * s) % MODULUS;
            index++;
        }

        prefixSum.add(0L);
        long currentSum = 0;
        for (int d : wDigits) {
            currentSum += d;
            prefixSum.add(currentSum);
        }

        long S = currentSum;
        int L = wDigits.size();

        byte[] R = new byte[(int) S + 1];
        long[] PModS = new long[L];

        for (int i = 0; i < L; ++i) {
            PModS[i] = prefixSum.get(i) % S;
        }

        for (int i = 0; i <= L; ++i) {
            R[(int) (prefixSum.get(i) % S)] = 1;
        }

        long[] pVals = new long[(int) S + 1];
        int numThreads = Math.max(1, Runtime.getRuntime().availableProcessors());
        long chunkSize = S / numThreads;

        ExecutorService executor = Executors.newFixedThreadPool(numThreads);
        List<Future<?>> futures = new ArrayList<>();

        for (int i = 0; i < numThreads; ++i) {
            final long startK = 1 + i * chunkSize;
            final long endK = (i == numThreads - 1) ? S : (startK + chunkSize - 1);

            if (startK <= endK) {
                futures.add(executor.submit(() -> {
                    for (long k = startK; k <= endK; ++k) {
                        long z = 1;
                        while (true) {
                            long startResidue = PModS[(int) ((z - 1) % L)];
                            long target = startResidue + k;
                            if (target >= S) {
                                target -= S;
                            }

                            if (R[(int) target] == 1) {
                                pVals[(int) k] = z;
                                break;
                            }
                            z++;
                        }
                    }
                }));
            }
        }

        for (Future<?> f : futures) {
            try {
                f.get();
            } catch (Exception e) {
            }
        }
        executor.shutdown();

        long numPeriods = LIMIT / S;
        long remainder = LIMIT % S;

        long sumPKOnePeriod = 0;
        long sumPKRemainder = 0;

        for (int k = 1; k <= S; ++k) {
            sumPKOnePeriod += pVals[k];
        }

        for (int k = 1; k <= remainder; ++k) {
            sumPKRemainder += pVals[k];
        }

        long totalAns = numPeriods * sumPKOnePeriod + sumPKRemainder;
        return String.valueOf(totalAns);
    }

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