BLAMOEBA - Super Amoeba
Peter has an amoeba farm with pretty much unlimited amoebae. After years of research, Peter created a device to convert some amoebae to super amoebae. However, his device can only be used once. Every day, a super amoeba will split into M super amoebae (2 < M < 100000).
Now, Peter plan his amoeba selling business. Initially, Peter converts X amoebae to super amoebae (X > 1). Every day after the amoebae split, Peter will take Y super amoebae for sale (Y > 1). After N days, Peter want all of his amoebae to be completely sold out (1 < N < 100000). Since the energy needed to convert amoebae is quite massive, X must be as small as possible. Help peter plan his business!
Input
First line is T, number of test cases (T < 100000). Next T lines each contains M and N separated by space.
Output
For each case, output X and Y separated by space. Since X and Y can be very large, output them with modulo 1000000007.
Example
Input: 1
4 3 Output: 21 64
Explanation
Initially, Peter has 21 super amoebae.
After day 1, there are 4 x 21 - 64 = 20 super amoebae
After day 2, there are 4 x 20 - 64 = 16 super amoebae
After day 3, there are 4 x 16 - 64 = 0 super amoeba
All the super amoebae are sold out after the 3rd day just as planned.
hide comments
Andy:
2016-09-05 10:05:18
overflow |
|
prabhakar_jha:
2016-09-05 09:51:45
Andy can you please look up at my solution i don't know why am i getting WA even i have tried some of my custom test cases for the submission 17652458
|
|
Andy:
2016-09-05 06:05:53
updated the description |
|
[Rampage] Blue.Mary:
2016-09-05 06:00:47
According to the explanation, the input numbers should be "M and N separated by space." |
Added by: | Andy |
Date: | 2016-09-04 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |
Resource: | BLPCS4 |