Under construction

Still being built. Things may change

Binomial Coefficient 2

Interview

Time limit1sMemory limit256 MB

Summary
Compute the binomial coefficient C(N, K) modulo 10007 for N up to 1000.
Level

Easy3 of 10

Topics
Dynamic programming, Combinatorics
Solved
No attempts yet

Problem

Given a natural number NN and an integer KK, write a program that computes the binomial coefficient (NK)\binom{N}{K} modulo 10,007.

Input

The first line contains NN and KK, separated by a space. (1≤N≤1,0001 \le N \le 1{,}000, 0≤K≤N0 \le K \le N)

Output

Print (NK)\binom{N}{K} modulo 10,007 on the first line.

Examples5

  1. Example 1

    Input
    5 2
    Expected output
    10

  2. Example 2

    Input
    1 0
    Expected output
    1

  3. Example 3

    Input
    1 1
    Expected output
    1

  4. Example 4

    Input
    2 1
    Expected output
    2

  5. Example 5

    Input
    10 5
    Expected output
    252