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:
20180401 00:39:56
someone help me solve this problem. 

Vipul Srivastava:
20170205 11:13:44
@ Andy shouldn't the answer for 898 655 be 331818851 141507265 for minimum X? 

Shashank Tiwari:
20161101 12:52:05
For input :


goelnandan:
20161026 21:58:01
Andy can you give some test case.


Andy:
20160908 14:10:24
Try learning some math 

guna_1998:
20160908 10:56:51
Last edit: 20160908 22:01:19 

prabhakar_jha:
20160905 10:52:54
thnx bro for your help


Andy:
20160905 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:
20160905 10:48:56
thnx Andy


Andy:
20160905 10:44:51
Java long can only store up to 64 bit (roughly 10^19). 
Added by:  Andy 
Date:  20160904 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 
Resource:  BLPCS4 