SPOJ Brasil

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 × 21 - 64 = 20 super amoebae
After day 2, there are 4 × 20 - 64 = 16 super amoebae
After day 3, there are 4 × 16 - 64 = 0 super amoeba
All the super amoebae are sold out after the 3rd day just as planned.