import java.util.*;

public class Euler350 {

    static final long MOD = 104060401L;

    static long modPow(long base, long exp) {
        long result = 1;
        base %= MOD;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * base) % MOD;
            }
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return result;
    }

    static int[] buildSpf(int n) {
        int[] spf = new int[n + 1];
        for (int i = 0; i <= n; i++)
            spf[i] = i;

        for (int i = 2; i * i <= n; i++) {
            if (spf[i] == i) {
                for (int j = i * i; j <= n; j += i) {
                    if (spf[j] == j) {
                        spf[j] = i;
                    }
                }
            }
        }
        return spf;
    }

    static long solve(long G, long L, long N) {
        int K = (int) (L / G);
        int[] spf = buildSpf(K);

        int maxExp = 0;
        int x = K;
        while (x > 0) {
            x /= 2;
            maxExp++;
        }

        long[] pows = new long[maxExp + 2];
        for (int b = 0; b <= maxExp + 1; b++) {
            if (b == 0) {
                pows[b] = 0;
            } else {
                pows[b] = modPow(b, N);
            }
        }

        long[] local = new long[maxExp + 1];
        for (int a = 1; a <= maxExp; a++) {
            long value = (pows[a + 1] - 2 * pows[a] % MOD + MOD) % MOD;
            value = (value + pows[a - 1]) % MOD;
            local[a] = value;
        }

        long[] h = new long[K + 1];
        h[1] = 1;

        for (int n = 2; n <= K; n++) {
            int cx = n;
            long value = 1;

            while (cx > 1) {
                int p = spf[cx];
                int e = 0;
                while (cx % p == 0) {
                    cx /= p;
                    e++;
                }
                value = (value * local[e]) % MOD;
            }
            h[n] = value;
        }

        long answer = 0;
        for (int m = 1; m <= K; m++) {
            long weight = L / m - G + 1;
            long w = weight % MOD;
            answer = (answer + h[m] * w) % MOD;
        }

        return answer;
    }

    public static String solve() {
        long ans = solve(1000000L, 1000000000000L, 1000000000000000000L);
        return String.valueOf(ans);
    }

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