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
rps21:
2018-04-01 00:39:56
someone help me solve this problem. |
|
Vipul Srivastava:
2017-02-05 11:13:44
@ Andy shouldn't the answer for 898 655 be 331818851 141507265 for minimum X? |
|
Shashank Tiwari:
2016-11-01 12:52:05
For input :
|
|
goelnandan:
2016-10-26 21:58:01
Andy can you give some test case.
|
|
Andy:
2016-09-08 14:10:24
Try learning some math |
|
prabhakar_jha:
2016-09-05 10:52:54
thnx bro for your help
|
|
Andy:
2016-09-05 10:50:33
Getting the logic is the easy part, the hard part is working around large power with modulo and division. You will need to learn modular exponentiation and modular inverse to solve this problem. |
|
prabhakar_jha:
2016-09-05 10:48:56
thnx Andy
|
|
Andy:
2016-09-05 10:44:51
Java long can only store up to 64 bit (roughly 10^19). |
|
prabhakar_jha:
2016-09-05 10:20:30
thnx andy for your response
|
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 |