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 :
5
4 3
50 40
75 16
898 655
1010 100

Output should be :
21 64
763876909 429968283
781408371 824219056
663637702 283014530
243204793 393634423

goelnandan: 2016-10-26 21:58:01

Andy can you give some test case.
finally did can't believe i was taking wrong datatype

Last edit: 2016-10-26 23:12:37
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
helped me a lot
thnx again

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 i will fix the overflow problem other than that am i logically correct for inputs where i will not get overflow?
@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
andy i am using mod 1000000007 and using long then how i am getting overflow can you please tell.
I am a beginner please help
@Andy

Last edit: 2016-09-05 10:23:17

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