Under construction

Still being built. Things may change

Padaengi's Cake Stacking

Time limit1sMemory limit1024 MB

Summary
Given N layer types with K copies each in random order, find the probability that every layer can be placed, modulo 1,000,000,007.
Level

Medium7 of 10

Topics
Combinatorics, Probability, Math
Solved
No attempts yet

Problem

Padaengi has loved sweet food since childhood, and wanted to make sweets with her own hands, so she took an internship at a food company.

The first task Padaengi receives is stacking NN cake layers. Padaengi must finish KK cakes every day. Each cake is stacked from the bottom layer to the top layer in order. Layer 1 can be placed right away. For an integer i≥1i \ge 1, layer i+1i+1 can be placed only on a cake whose stack has layers 1 through ii and nothing above.

While working every day, Padaengi noticed that she often receives a layer that cannot be placed. She considers this a serious problem for her work efficiency. To raise the issue, she decided to report the probability that no layer that cannot be placed is received during the work, when the layers are given in a random order. Calculate this probability for Padaengi!

Input

The first line contains the number of cake layers NN and the number of cakes KK to make, separated by a space. (1≤N≤1,0001 \le N \le 1{,}000, 1≤K≤1,0001 \le K \le 1{,}000)

Output

When N×KN \times K cake layers are given in a random order, let the probability that no layer that cannot be placed is received during the work be p/qp / q. Print p×q−1(mod1,000,000,007)p \times q^{-1} \pmod{1{,}000{,}000{,}007}. Here q−1q^{-1} is the modular multiplicative inverse of qq, and pp and qq are coprime. Under the given constraints, the value of p×q−1(mod1,000,000,007)p \times q^{-1} \pmod{1{,}000{,}000{,}007} is proven to exist uniquely.

1,000,000,007=109+71{,}000{,}000{,}007 = 10^9+7

Hint

The N×KN \times K cake layers consist of KK layers each of NN types.

Examples1

  1. Example 1

    Input
    2 5
    
    Expected output
    166666668