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

public class Euler511 {
    static class Factor {
        long p;
        int e;

        Factor(long p, int e) {
            this.p = p;
            this.e = e;
        }
    }

    static List<Long> getDivisors(long n) {
        List<Factor> factors = new ArrayList<>();
        long x = n;
        for (long p = 2; p * p <= x; p += (p == 2 ? 1 : 2)) {
            if (x % p == 0) {
                int e = 0;
                while (x % p == 0) {
                    e++;
                    x /= p;
                }
                factors.add(new Factor(p, e));
            }
        }
        if (x > 1) {
            factors.add(new Factor(x, 1));
        }

        List<Long> divs = new ArrayList<>();
        buildDivisors(factors, 0, 1L, divs);
        return divs;
    }

    static void buildDivisors(List<Factor> factors, int idx, long current, List<Long> divs) {
        if (idx == factors.size()) {
            divs.add(current);
            return;
        }
        Factor f = factors.get(idx);
        long val = 1;
        for (int i = 0; i <= f.e; i++) {
            buildDivisors(factors, idx + 1, current * val, divs);
            val *= f.p;
        }
    }

    static int[] cyclicConvolution(int[] a, int[] b, int mod) {
        int k = a.length;
        long[] out = new long[k];
        for (int i = 0; i < k; i++) {
            long ai = a[i];
            if (ai == 0)
                continue;
            int split = k - i;
            for (int j = 0; j < split; j++) {
                out[i + j] += ai * b[j];
                if (out[i + j] >= 4000000000000000000L) { // Prevent overflow
                    out[i + j] %= mod;
                }
            }
            for (int j = split; j < k; j++) {
                out[i + j - k] += ai * b[j];
                if (out[i + j - k] >= 4000000000000000000L) {
                    out[i + j - k] %= mod;
                }
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = (int) (out[i] % mod);
        }
        return res;
    }

    static int[] cyclicPower(int[] base, long exp, int mod) {
        int k = base.length;
        int[] res = new int[k];
        res[0] = 1;

        while (exp > 0) {
            if ((exp & 1) == 1) {
                res = cyclicConvolution(res, base, mod);
            }
            exp >>= 1;
            if (exp > 0) {
                base = cyclicConvolution(base, base, mod);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        long n = 1234567898765L;
        int k = 4321;
        int mod = 1000000000;

        List<Long> divisors = getDivisors(n);
        int[] base = new int[k];
        for (long d : divisors) {
            base[(int) (d % k)]++;
        }

        int[] ways = cyclicPower(base, n, mod);
        int target = (int) ((k - (n % k)) % k);

        System.out.printf("%09d\n", ways[target]);
    }
}