You are given the first term (A), the common ratio (R) and an integer N. Your task is to find the Nth term of the GP series.

The general form of a GP(Geometric Progression) series is A, A(R), A(R^2), A*(R^3) and so on where A is the first term of GP series

Note :

As the answer can be large enough, return the answer modulo 10^9 + 7.

Input format :

The first line of input contains an integer T denoting the number of queries or test cases. 

The first line of every test case contains three single space-separated integers N, A, and R denoting the term of GP series required, the first term, and the common ratio respectively. 

Output format :

For each test case, print an integer denoting the Nth term of GP in a separate line. 

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^8
0 <= A <= 50 
0 <= R <= 100

Time limit: 1 second