2017 ACM-ICPC西安网赛B-Coin

B-Coin

Bob has a not even coin, every time he tosses the coin, the probability that the coin's front face up is frac{q}{p}(frac{q}{p} le frac{1}{2})​p​​q​​(​p​​q​​≤​2​​1​​).

The question is, when Bob tosses the coin kktimes, what's the probability that the frequency of the coin facing up is even number.

If the answer is frac{X}{Y}​Y​​X​​, because the answer could be extremely large, you only need to print (X * Y^{-1}) mod (10^9+7)(X∗Y​−1​​)mod(10​9​​+7).

Input Format

First line an integer TT, indicates the number of test cases (T le 100T≤100).

Then Each line has 33 integer p,q,k(1le p,q,k le 10^7)p,q,k(1≤p,q,k≤10​7​​) indicates the i-th test case.

Output Format

For each test case, print an integer in a single line indicates the answer.

样例输入

2
2 1 1
3 1 2

样例输出

500000004
555555560

题目来源

2017 ACM-ICPC 亚洲区（西安赛区）网络赛

//2017-10-24
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long

using namespace std;

const int MOD = 1000000007;

ll quickPow(ll a, ll n){
    ll ans = 1;
    while(n){
        if(n&1)
            ans = (a*ans)%MOD;
        a = (a*a)%MOD;
        n >>= 1;
    }
    return ans;
}

int main()
{
    ll p, q, k, T;
    cin>>T;
    while(T--){
        cin>>p>>q>>k;
        ll X = quickPow(p-2*q, k);
        ll Y = quickPow(p, k);
        cout<<(((1+X*quickPow(Y, MOD-2))%MOD) * quickPow(2, MOD-2))%MOD<<endl;
    }

    return 0;
}