BANSTAND - Colored Development
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 expected number of distinct colors in the rainbow after all the layers are colored in this way.
1 ≤ T ≤ 10
1 ≤ N, M ≤ 2 * 105
Development Colored
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 two integers, N and M.Constraints
Output
For each test case, print the case number and the expected number of distinct colors in the rainbow after all the layers are colored. Formally, let the expected number of distinct colors 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 2 2 4 2
Sample Output
Case 1: 1 Case 2: 500000005 Case 3: 750000007
Challenge
Too easy? Try the harder version here:Development Colored
hide comments
nacly_fish:
2022-06-25 19:54:56
Nice problem. It would be more interesting if n,m ≤ 1e18. |
Added by: | sgtlaugh |
Date: | 2020-05-21 |
Time limit: | 10s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Own Problem, Used in 2019-2020 ACM-ICPC Asia Dhaka Regional Contest |