Padaengi's Cake Stacking
Time limit1sMemory limit1024 MB
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 cake layers. Padaengi must finish 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 , layer can be placed only on a cake whose stack has layers 1 through 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 and the number of cakes to make, separated by a space. (, )
Output
When cake layers are given in a random order, let the probability that no layer that cannot be placed is received during the work be . Print . Here is the modular multiplicative inverse of , and and are coprime. Under the given constraints, the value of is proven to exist uniquely.
Hint
The cake layers consist of layers each of types.