SimpleOne

You are given the equation tanα=pq and a positive integer, n. Calculate tannα. There are T test cases.

Input Format

The first line contains T, the number of test cases. 
The next T lines contain three space separated integers: p,q and n, respectively.

Constraints 
0⩽p⩽109 
1⩽q⩽109 
1⩽n⩽109 
T⩽104
Output Format

If the result is defined, it is always a rational number. However, it can be very big. 
Output the answer modulo (109+7). 
If the answer is ab and b is not divisible by (109+7), there is a unique integer 0⩽x<109+7 where a≡bxmod(109+7). 
Output this integer, x. 
It is guaranteed that b is not divisible by (109+7) for all test cases.

Sample Input

2
2 1 2
5 6 7
Sample Output

JAVA SOLUTION:
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class B {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		for(int T = ni();T > 0;T--){
			long p = nl(), q = nl(), n = nl();
			long num = p, den = q;
			long rnum = 0, rden = 1;
			int mod = 1000000007;
			while(n > 0){
				if((n&1) == 1){
					// num/den+rnum/rden
					// ------------------
					// 1-num*rnum/den/rden
					// num*rden+rnum*den
					// den*rden-num*rnum
					long nrnum = num*rden+rnum*den;
					long nrden = den*rden-num*rnum;
					nrnum %= mod;
					nrden %= mod;
					if(nrden < 0)nrden += mod;
					rnum = nrnum; rden = nrden;
				}
				
				long nnum = num*den+num*den;
				long nden = den*den-num*num;
				nnum %= mod;
				nden %= mod;
				if(nden < 0)nden += mod;
				num = nnum; den = nden;
				n>>>=1;
			}
			out.println(rnum*invl(rden,mod)%mod);
		}
	}
	
	public static long invl(long a, long mod) {
		long b = mod;
		long p = 1, q = 0;
		while (b > 0) {
			long c = a / b;
			long d;
			d = a;
			a = b;
			b = d % b;
			d = p;
			p = q;
			q = d - c * q;
		}
		return p < 0 ? p + mod : p;
	}
	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static void main(String[] args) throws Exception { new B().run(); }
	
	private byte[] inbuf = new byte[1024];
	private int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
C++ SOLUTION
#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const i64 P = 1000000000 + 7;

i64 deg(i64 x, i64 d) {
    x %= P;
    d %= P - 1;
    if (d < 0) d += P - 1;
    i64 y = 1;
    while (d) {
        if (d & 1) y *= x, y %= P;
        x *= x, x %= P;
        d /= 2;
    }
    return y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif

    int T;
    cin >> T;
    forn(t, T) {
        i64 p, q, n;
        cin >> p >> q >> n;
        p *= deg(q, -1); p %= P;
        i64 y = 0;
        while (n) {
            if (n & 1) y = (y + p) * deg(1 - y * p, -1), y %= P;
            p = (p + p) * deg(1 - p * p, -1), p %= P;
            n /= 2;
        }
        if (y < 0) y += P;
        cout << y << '\n';
    }

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


666666670
237627959
Explanation

If tanα=21 then tan2α=−43 and −4≡3×666666670mod(109+7). 
So, the answer is 666666670.

Super python solution:
read = lambda: map(int, input().split())

P = 10**9 + 7

def mul(a, b):
    return ((a[0] * b[0] - a[1] * b[1]) % P, (a[0] * b[1] + a[1] * b[0]) % P)

def my_pow(a, b):
    ret = (1, 0)
    while b > 0:
        if (b & 1) == 1:
            ret = mul(ret, a)
        a = mul(a, a)
        b >>= 1
    return ret

n, = read()
for _ in range(n):
    p, q, n = read()
    a = my_pow((q, p), n)
    print(a[1] * pow(a[0], P - 2, P) % P)