import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Euler550 {
    static final long MOD = 987654321L;

    static long modPow(long a, long e) {
        a %= MOD;
        long r = 1 % MOD;
        while (e > 0) {
            if ((e & 1) != 0)
                r = (r * a) % MOD;
            a = (a * a) % MOD;
            e >>= 1;
        }
        return r;
    }

    static long[] extGcd(long a, long b) {
        if (b == 0)
            return new long[] { a, 1, 0 };
        long[] res = extGcd(b, a % b);
        long g = res[0];
        long x1 = res[1];
        long y1 = res[2];
        return new long[] { g, y1, x1 - (a / b) * y1 };
    }

    static long modInv(long a) {
        long[] res = extGcd(a % MOD, MOD);
        long x = res[1] % MOD;
        if (x < 0)
            x += MOD;
        return x;
    }

    static void fwhtXor(long[] a, boolean inverse) {
        int n = a.length;
        for (int len = 1; len < n; len <<= 1) {
            for (int i = 0; i < n; i += (len << 1)) {
                for (int j = 0; j < len; j++) {
                    long u = a[i + j];
                    long v = a[i + j + len];
                    long x = u + v;
                    if (x >= MOD)
                        x -= MOD;
                    long y = u - v;
                    if (y < 0)
                        y += MOD;
                    a[i + j] = x;
                    a[i + j + len] = y;
                }
            }
        }
        if (inverse) {
            long invN = modInv(n);
            for (int i = 0; i < n; i++) {
                a[i] = (a[i] * invN) % MOD;
            }
        }
    }

    static class GrundyComputer {
        Map<Long, Integer> memo = new HashMap<>();

        int grundy(long key) {
            if (memo.containsKey(key))
                return memo.get(key);

            List<Integer> aList = new ArrayList<>();
            long tempKey = key;
            int aLen = (int) (tempKey >>> 60);
            for (int i = 0; i < aLen; i++) {
                aList.add((int) ((tempKey >> (6 * i)) & 63L));
            }

            int[] a = new int[aLen];
            for (int i = 0; i < aLen; i++)
                a[i] = aList.get(i);

            int[] cur = new int[aLen];
            List<Integer> divNims = new ArrayList<>();

            dfs(0, false, true, a, cur, divNims);

            if (divNims.isEmpty()) {
                memo.put(key, 0);
                return 0;
            }

            Collections.sort(divNims);
            List<Integer> uniqueNims = new ArrayList<>();
            for (int v : divNims) {
                if (uniqueNims.isEmpty() || uniqueNims.get(uniqueNims.size() - 1) != v) {
                    uniqueNims.add(v);
                }
            }

            int mx = uniqueNims.get(uniqueNims.size() - 1);
            boolean[] present = new boolean[mx + 1];
            for (int v : uniqueNims)
                present[v] = true;

            int mex = 0;
            while (true) {
                boolean ok = false;
                for (int v : uniqueNims) {
                    int t = v ^ mex;
                    if (t <= mx && present[t]) {
                        ok = true;
                        break;
                    }
                }
                if (!ok)
                    break;
                mex++;
            }

            memo.put(key, mex);
            return mex;
        }

        void dfs(int idx, boolean anyPos, boolean allEq, int[] a, int[] cur, List<Integer> divNims) {
            if (idx == a.length) {
                if (!anyPos)
                    return;
                if (allEq)
                    return;

                int[] b = new int[a.length];
                int blen = 0;
                for (int i = 0; i < a.length; i++) {
                    if (cur[i] > 0)
                        b[blen++] = cur[i];
                }
                for (int i = 1; i < blen; i++) {
                    int v = b[i];
                    int j = i;
                    while (j > 0 && b[j - 1] < v) {
                        b[j] = b[j - 1];
                        j--;
                    }
                    b[j] = v;
                }

                long dkey = ((long) blen) << 60;
                for (int i = 0; i < blen; i++) {
                    dkey |= ((long) b[i]) << (6 * i);
                }
                divNims.add(grundy(dkey));
                return;
            }
            for (int e = 0; e <= a[idx]; e++) {
                cur[idx] = e;
                dfs(idx + 1, anyPos || (e > 0), allEq && (e == a[idx]), a, cur, divNims);
            }
        }
    }

    static int[] buildSpf(int n) {
        int[] spf = new int[n + 1];
        int numPrimes = 0;
        int maxPrimes = Math.max(1000, (int) (n / Math.max(1, Math.log(n)) * 1.2));
        int[] primes = new int[maxPrimes];

        for (int i = 2; i <= n; i++) {
            if (spf[i] == 0) {
                spf[i] = i;
                if (numPrimes < primes.length) {
                    primes[numPrimes++] = i;
                } else {
                    int[] newPrimes = new int[primes.length * 2];
                    System.arraycopy(primes, 0, newPrimes, 0, primes.length);
                    primes = newPrimes;
                    primes[numPrimes++] = i;
                }
            }
            for (int j = 0; j < numPrimes; j++) {
                int p = primes[j];
                long v = (long) p * i;
                if (v > n)
                    break;
                spf[(int) v] = p;
                if (p == spf[i])
                    break;
            }
        }
        return spf;
    }

    static long winningPositions(int n, long k, GrundyComputer gc) {
        int[] spf = buildSpf(n);

        long[] counts = new long[1];
        int maxG = 0;

        int[] exps = new int[32];
        for (int x = 2; x <= n; x++) {
            int t = x;
            int len = 0;
            while (t > 1) {
                int p = spf[t];
                int c = 0;
                while (t > 1 && spf[t] == p) {
                    t /= p;
                    c++;
                }
                exps[len++] = c;
            }
            for (int i = 1; i < len; i++) {
                int v = exps[i];
                int j = i;
                while (j > 0 && exps[j - 1] < v) {
                    exps[j] = exps[j - 1];
                    j--;
                }
                exps[j] = v;
            }

            long key = ((long) len) << 60;
            for (int i = 0; i < len; i++) {
                key |= ((long) exps[i]) << (6 * i);
            }

            int g = gc.grundy(key);
            if (g >= counts.length) {
                long[] newCounts = new long[g + 1];
                System.arraycopy(counts, 0, newCounts, 0, counts.length);
                counts = newCounts;
            }
            counts[g]++;
            if (g > maxG)
                maxG = g;
        }

        int sz = 1;
        while (sz <= maxG)
            sz <<= 1;
        long[] a = new long[sz];
        for (int i = 0; i < counts.length; i++) {
            a[i] = counts[i] % MOD;
        }

        fwhtXor(a, false);
        for (int i = 0; i < a.length; i++) {
            a[i] = modPow(a[i], k);
        }
        fwhtXor(a, true);

        long losing = a[0] % MOD;
        long total = modPow(n - 1, k);
        long ans = (total + MOD - losing) % MOD;
        return ans;
    }

    public static String solve() {
        GrundyComputer gc = new GrundyComputer();
        return Long.toString(winningPositions(10000000, 1000000000000L, gc));
    }

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