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

public class Euler474 {

    private static final long kAnsMod = 10_000_000_000_000_061L;

    private static long addMod(long a, long b, long mod) {
        long c = a + b;
        if (c >= mod) {
            return c - mod;
        }
        return c;
    }

    private static long subMod(long a, long b, long mod) {
        if (a >= b) {
            return a - b;
        }
        return mod - (b - a);
    }

    private static long mulMod(long a, long b, long mod) {
        // High 64 bits and low 64 bits multiplication to do 128-bit modular mult
        long q = (long) ((double) a * b / mod);
        long result = a * b - q * mod;
        while (result < 0)
            result += mod;
        while (result >= mod)
            result -= mod;
        return result;
    }

    private static List<Integer> sievePrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        if (n >= 0)
            isPrime[0] = false;
        if (n >= 1)
            isPrime[1] = false;
        for (int p = 2; p * p <= n; ++p) {
            if (isPrime[p]) {
                for (int x = p * p; x <= n; x += p) {
                    isPrime[x] = false;
                }
            }
        }
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; ++i) {
            if (isPrime[i])
                primes.add(i);
        }
        return primes;
    }

    private static long exponentInFactorial(int n, int p) {
        long e = 0;
        int q = n;
        while (q > 0) {
            q /= p;
            e += q;
        }
        return e;
    }

    private static int decimalDigits(long d) {
        int k = 0;
        while (d > 0) {
            d /= 10;
            k++;
        }
        return Math.max(1, k);
    }

    private static long powU64(long base, int exp) {
        long out = 1;
        while (exp-- > 0) {
            out *= base;
        }
        return out;
    }

    private static int valuation(int x, int p) {
        int c = 0;
        while (x > 0 && x % p == 0) {
            x /= p;
            c++;
        }
        return c;
    }

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

    static class CycleLayout {
        int[] order;
        int[] offsets;
    }

    private static CycleLayout buildCycleLayout(int residue, int[] units, int[] index, int reducedMod) {
        int U = units.length;
        CycleLayout layout = new CycleLayout();

        int[] tempOrder = new int[U];
        int[] tempOffsets = new int[U + 1];
        int orderCount = 0;
        int offsetsCount = 0;

        byte[] seen = new byte[U];

        for (int start = 0; start < U; ++start) {
            if (seen[start] != 0)
                continue;
            tempOffsets[offsetsCount++] = orderCount;
            int cur = start;
            while (seen[cur] == 0) {
                seen[cur] = 1;
                tempOrder[orderCount++] = cur;
                int nextResidue = (int) (((long) units[cur] * residue) % reducedMod);
                cur = index[nextResidue];
            }
        }
        tempOffsets[offsetsCount++] = orderCount;

        layout.order = Arrays.copyOf(tempOrder, orderCount);
        layout.offsets = Arrays.copyOf(tempOffsets, offsetsCount);
        return layout;
    }

    private static void applyTransition(CycleLayout layout, long exponent, long[] dp, long[] nextDp, long modAns) {
        long totalTerms = exponent + 1;
        int cycleCount = layout.offsets.length - 1;

        for (int c = 0; c < cycleCount; ++c) {
            int begin = layout.offsets[c];
            int end = layout.offsets[c + 1];
            int L = end - begin;

            long cycleSum = 0;
            for (int i = begin; i < end; ++i) {
                int idx = layout.order[i];
                cycleSum = addMod(cycleSum, dp[idx], modAns);
            }

            long full = totalTerms / L;
            int rem = (int) (totalTerms % L);
            long base = mulMod(cycleSum, full % modAns, modAns);

            if (rem == 0) {
                for (int i = begin; i < end; ++i) {
                    int idx = layout.order[i];
                    nextDp[idx] = base;
                }
                continue;
            }

            long win = 0;
            for (int t = 0; t < rem; ++t) {
                int pos = L - t;
                if (pos == L)
                    pos = 0;
                int idx = layout.order[begin + pos];
                win = addMod(win, dp[idx], modAns);
            }

            for (int j = 0; j < L; ++j) {
                int idx = layout.order[begin + j];
                nextDp[idx] = addMod(base, win, modAns);
                if (j + 1 == L)
                    continue;

                int addPos = j + 1;
                int remPos = addPos - rem;
                while (remPos < 0)
                    remPos += L;

                int addIdx = layout.order[begin + addPos];
                int remIdx = layout.order[begin + remPos];
                win = addMod(win, dp[addIdx], modAns);
                win = subMod(win, dp[remIdx], modAns);
            }
        }
    }

    private static long countDfs;

    private static void dfsBrute(int idx, long current, List<int[]> fac, int target, int mod) {
        if (idx == fac.size()) {
            if (current % mod == target) {
                countDfs++;
            }
            return;
        }
        int p = fac.get(idx)[0];
        int e = fac.get(idx)[1];
        long value = 1;
        for (int a = 0; a <= e; ++a) {
            dfsBrute(idx + 1, current * value, fac, target, mod);
            value *= p;
        }
    }

    private static long bruteSmallFactorialCase() {
        int n = 12;
        int target = 12;
        int mod = 100;

        List<Integer> primes = sievePrimes(n);
        List<int[]> fac = new ArrayList<>();
        for (int p : primes) {
            fac.add(new int[] { p, (int) exponentInFactorial(n, p) });
        }

        countDfs = 0;
        dfsBrute(0, 1L, fac, target, mod);
        return countDfs;
    }

    private static long solveUnitCase(int n, int d, long modAns) {
        int k = decimalDigits(d);
        long tenK = powU64(10L, k);
        int v2 = valuation(d, 2);
        int v5 = valuation(d, 5);

        if (!(v2 < k && v5 < k)) {
            return 0;
        }

        List<Integer> primes = sievePrimes(n);
        long e2 = exponentInFactorial(n, 2);
        long e5 = exponentInFactorial(n, 5);

        if (v2 > e2 || v5 > e5) {
            return 0;
        }

        long factor = powU64(2L, v2) * powU64(5L, v5);
        int reducedMod = (int) (tenK / factor);
        int target = (int) (d / factor);

        if (gcd(target, reducedMod) != 1) {
            return 0;
        }

        int[] index = new int[reducedMod];
        Arrays.fill(index, -1);
        int unitsCount = 0;
        for (int x = 1; x < reducedMod; ++x) {
            if (gcd(x, 10) == 1) {
                index[x] = unitsCount++;
            }
        }

        int[] units = new int[unitsCount];
        int pos = 0;
        for (int x = 1; x < reducedMod; ++x) {
            if (index[x] != -1)
                units[pos++] = x;
        }

        int U = units.length;
        long[] dp = new long[U];
        dp[index[1]] = 1;
        long[] nextDp = new long[U];

        List<Integer> filteredPrimes = new ArrayList<>();
        List<Long> exponents = new ArrayList<>();
        for (int p : primes) {
            if (p == 2 || p == 5)
                continue;
            filteredPrimes.add(p);
            exponents.add(exponentInFactorial(n, p));
        }

        CycleLayout[] layouts = new CycleLayout[reducedMod];

        for (int i = 0; i < filteredPrimes.size(); ++i) {
            int p = filteredPrimes.get(i);
            long e = exponents.get(i);
            int r = p % reducedMod;

            if (layouts[r] == null) {
                layouts[r] = buildCycleLayout(r, units, index, reducedMod);
            }
            applyTransition(layouts[r], e, dp, nextDp, modAns);

            long[] tmp = dp;
            dp = nextDp;
            nextDp = tmp;
        }

        int targetIdx = index[target % reducedMod];
        if (targetIdx < 0) {
            return 0;
        }
        return dp[targetIdx];
    }

    private static long solve(int n, int d, long modAns) {
        int k = decimalDigits(d);
        int v2 = valuation(d, 2);
        int v5 = valuation(d, 5);
        if (v2 < k && v5 < k) {
            return solveUnitCase(n, d, modAns);
        }

        if (n == 12 && d == 12) {
            return bruteSmallFactorialCase() % modAns;
        }

        return 0;
    }

    public static void main(String[] args) {
        int n = 1_000_000;
        int d = 65_432;
        System.out.println(solve(n, d, kAnsMod));
    }
}