public class Euler824 {

    static final long P = 10000019L;
    static final long MOD = P * P;

    static long[] fact;
    static long[] H;
    static long[] invSmall;
    static long factPMinus1;

    static long mulMod(long a, long b) {
        // Since MOD is roughly 10^14, a*b can be 10^28, which overflows long (max
        // ~9e18).
        // Must use Math.multiplyHigh / 128-bit multiplication trick if available, or
        // BigInteger.
        // Or simply multiply in chunks.
        long q = (long) ((double) a * b / MOD);
        long r = a * b - q * MOD;
        while (r < 0)
            r += MOD;
        while (r >= MOD)
            r -= MOD;
        return r;
    }

    static long powMod(long base, long exp) {
        long res = 1;
        while (exp > 0) {
            if ((exp & 1) != 0)
                res = mulMod(res, base);
            base = mulMod(base, base);
            exp >>= 1;
        }
        return res;
    }

    static long modInv(long a, long mod) {
        long t = 0, newt = 1;
        long r = mod, newr = a;
        while (newr != 0) {
            long q = r / newr;
            long tmpt = t - q * newt;
            long tmpr = r - q * newr;
            t = newt;
            newt = tmpt;
            r = newr;
            newr = tmpr;
        }
        if (r != 1)
            return 0;
        if (t < 0)
            t += mod;
        return t;
    }

    static long vpFactorial(long n) {
        long e = 0;
        while (n > 0) {
            n /= P;
            e += n;
        }
        return e;
    }

    static long factWithoutP(long n) {
        if (n == 0)
            return 1;
        long q = n / P;
        long r = n % P;
        long res = factWithoutP(q);
        res = mulMod(res, powMod(factPMinus1, q));
        res = mulMod(res, fact[(int) r]);
        if (r != 0) {
            long qMod = q % P;
            long factor = 1;
            if (qMod != 0) {
                long tmp = mulMod(mulMod(qMod, P), H[(int) r]);
                factor = (1 + tmp) % MOD;
            }
            res = mulMod(res, factor);
        }
        return res;
    }

    static long binomModP2(long n, long k) {
        if (k > n)
            return 0;
        long e = vpFactorial(n) - vpFactorial(k) - vpFactorial(n - k);
        if (e >= 2)
            return 0;
        long a = factWithoutP(n);
        long b = factWithoutP(k);
        long c = factWithoutP(n - k);
        long denom = mulMod(b, c);
        long invDenom = modInv(denom, MOD);
        long res = mulMod(a, invDenom);
        if (e == 1)
            res = mulMod(res, P);
        return res;
    }

    static long coeffLambdaPlus(long m, long k) {
        if (k == 0)
            return 1;
        if (m == 0)
            return 0;
        long n = m - k - 1;
        long r = k - 1;
        long c = binomModP2(n, r);
        long invK = modInv(k % MOD, MOD);
        return mulMod(c, mulMod(m % MOD, invK));
    }

    static void initTables(int maxJ) {
        fact = new long[(int) P];
        fact[0] = 1;
        for (int i = 1; i < P; ++i) {
            fact[i] = mulMod(fact[i - 1], i);
        }
        factPMinus1 = fact[(int) (P - 1)];

        long[] inv = new long[(int) P];
        inv[1] = 1;
        for (int i = 2; i < P; ++i) {
            inv[i] = (MOD - mulMod(MOD / i, inv[(int) (MOD % i)])) % MOD;
        }

        H = new long[(int) P];
        for (int i = 1; i < P; ++i) {
            H[i] = (H[i - 1] + inv[i]) % MOD;
        }

        invSmall = new long[maxJ + 1];
        if (maxJ >= 1)
            invSmall[1] = inv[1];
        for (int i = 2; i <= maxJ; ++i) {
            invSmall[i] = inv[i];
        }
    }

    static long computeL(long N, long K) {
        int J = (int) (K / N);
        long[] binomN = new long[J + 1];
        binomN[0] = 1;
        for (int j = 0; j < J; ++j) {
            long num = (N - j) % MOD;
            if (num < 0)
                num += MOD;
            long next = mulMod(binomN[j], mulMod(num, invSmall[j + 1]));
            binomN[j + 1] = next;
        }

        long total = 0;
        for (int j = 0; j <= J; ++j) {
            long k = K - N * j;
            long coeff = coeffLambdaPlus(N * (N - 2L * j), k);
            long term = mulMod(binomN[j], coeff);
            if ((N & 1L) == 1L && (j & 1) == 1 && term != 0) {
                term = MOD - term;
            }
            total += term;
            if (total >= MOD)
                total -= MOD;
        }
        return total;
    }

    public static String solve() {
        long N = 1000000000L;
        long K = 1000000000000000L;
        int maxJ = (int) (K / N);

        initTables(maxJ);
        long ans = computeL(N, K);
        return Long.toString(ans);
    }

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