import java.util.ArrayList;
import java.util.List;

public class Euler440 {
    private static final int MOD = 987898789;
    private static final int LIMIT = 2000;

    private static class Mat2 {
        long a00, a01, a10, a11;

        Mat2(long a00, long a01, long a10, long a11) {
            this.a00 = a00;
            this.a01 = a01;
            this.a10 = a10;
            this.a11 = a11;
        }
    }

    private static long modPow(long base, long exp, long mod) {
        long result = 1;
        long cur = (base % mod + mod) % mod;
        long e = exp;
        while (e > 0) {
            if ((e & 1) != 0) {
                result = (result * cur) % mod;
            }
            cur = (cur * cur) % mod;
            e >>= 1;
        }
        return result;
    }

    private static Mat2 mul(Mat2 x, Mat2 y) {
        return new Mat2(
                (x.a00 * y.a00 + x.a01 * y.a10) % MOD,
                (x.a00 * y.a01 + x.a01 * y.a11) % MOD,
                (x.a10 * y.a00 + x.a11 * y.a10) % MOD,
                (x.a10 * y.a01 + x.a11 * y.a11) % MOD);
    }

    private static Mat2 matPow(Mat2 base, long exp) {
        Mat2 result = new Mat2(1, 0, 0, 1);
        long e = exp;
        while (e > 0) {
            if ((e & 1) != 0) {
                result = mul(result, base);
            }
            e >>= 1;
            if (e > 0) {
                base = mul(base, base);
            }
        }
        return result;
    }

    private static long sequencePeriod() {
        Mat2 A = new Mat2(10, 1, 1, 0);
        long leg = modPow(104 % MOD, (MOD - 1) / 2, MOD);
        long candidate = (leg == 1) ? (MOD - 1) : (MOD + 1);

        long period = candidate;
        long x = candidate;
        List<long[]> fac = new ArrayList<>();
        for (long p = 2; p * p <= x; p++) {
            if (x % p == 0) {
                int e = 0;
                while (x % p == 0) {
                    x /= p;
                    e++;
                }
                fac.add(new long[] { p, e });
            }
        }
        if (x > 1) {
            fac.add(new long[] { x, 1 });
        }

        for (long[] f : fac) {
            long q = f[0];
            while (period % q == 0) {
                long trial = period / q;
                Mat2 pMat = matPow(A, trial);
                if (pMat.a00 == 1 && pMat.a01 == 0 && pMat.a10 == 0 && pMat.a11 == 1) {
                    period = trial;
                } else {
                    break;
                }
            }
        }
        return period;
    }

    private static List<Mat2> buildPowersForT() {
        List<Mat2> pw = new ArrayList<>();
        pw.add(new Mat2(10, 1, 1, 0));
        for (int i = 1; i < 64; i++) {
            pw.add(mul(pw.get(i - 1), pw.get(i - 1)));
        }
        return pw;
    }

    private static long tModFromIndex(long n, List<Mat2> pw) {
        if (n == 0)
            return 1;

        long v0 = 10;
        long v1 = 1;
        long e = n - 1;
        int bit = 0;
        while (e > 0) {
            if ((e & 1) != 0) {
                Mat2 m = pw.get(bit);
                long nv0 = (m.a00 * v0 + m.a01 * v1) % MOD;
                long nv1 = (m.a10 * v0 + m.a11 * v1) % MOD;
                v0 = nv0;
                v1 = nv1;
            }
            e >>= 1;
            bit++;
        }
        return v0;
    }

    private static int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    public static String solve() {
        int l = LIMIT;
        long period = sequencePeriod();
        List<Mat2> pw = buildPowersForT();

        long[] countsSame = new long[l + 1];
        int[] v2 = new int[l + 1];
        for (int x = 1; x <= l; x++) {
            v2[x] = Integer.numberOfTrailingZeros(x);
        }

        for (int a = 1; a <= l; a++) {
            int ta = v2[a];
            for (int b = 1; b <= l; b++) {
                if (v2[b] != ta)
                    continue;
                int g = gcd(a, b);
                countsSame[g]++;
            }
        }

        long sameTotal = 0;
        for (int d = 1; d <= l; d++) {
            sameTotal += countsSame[d];
        }
        long totalPairs = (long) l * l;
        long countDiff = totalPairs - sameTotal;

        long[] countsSameMod = new long[l + 1];
        for (int d = 1; d <= l; d++) {
            countsSameMod[d] = countsSame[d] % MOD;
        }

        long ans = 0;
        for (int c = 1; c <= l; c++) {
            long base = (c % 2 != 0) ? 10 : 1;
            long sumC = ((countDiff % MOD) * base) % MOD;

            long p = 1;
            for (int d = 1; d <= l; d++) {
                p = (p * c) % period;
                long tval = tModFromIndex(p, pw);
                sumC = (sumC + countsSameMod[d] * tval) % MOD;
            }
            ans = (ans + sumC) % MOD;
        }

        return String.valueOf(ans);
    }

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