STANDBAN - Development Colored
There are N unique colors in the universe, numbered from 1 to N. George Michael wants to create a rainbow using these colors. The rainbow will consist of exactly M layers. For each layer, George Michael selects a color uniformly randomly from the N colors and colors the layer with it.
George Michael wonders what will be the probability that there will be at least K distinct colors in the rainbow after all the layers are colored in this way.
1 ≤ T ≤ 20
1 ≤ N, M, K ≤ 2 * 105
Input
The first line of the input contains an integer T, denoting the number of test cases. Each of the next T lines will contain three integers, N, M and K.Constraints
Output
For each test case, print the case number and the probability that the rainbow will contain at least K distinct colors after all the layers are colored. Formally, let this probability be an irreducible fraction P / Q. Then you need to print (P * Q-1) modulo 1000000007, where Q-1 is the modular inverse of Q modulo 1000000007. You may safely assume that there will be a unique modular inverse of Q modulo 1000000007.Sample Input
3 1 1 1 2 2 2 4 2 2
Sample Output
Case 1: 1 Case 2: 500000004 Case 3: 750000006
Challenge(!)
Colored Developmenthide comments
nacly_fish:
2022-06-25 19:07:34
In fact, fft is unnecessary in this problem. You can solve it in O(n \log_k n) time complexity. |
|
[Rampage] Blue.Mary:
2020-05-22 06:11:12
Since this problem is "too hard" (actually not...), I've found the simple solution to the previous version.
|
Added by: | sgtlaugh |
Date: | 2020-05-22 |
Time limit: | 10s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Own Problem |