Chef has a clock, but it got broken today — the minute hand on Chef's clock doesn't rotate by the angle 2π/3600 each second, but by a different fixed angle x. The coordinates of the center of the clock are (0, 0). The length of the minute hand is l.

One endpoint of the minute hand is always located at the clock center; the other endpoint is initially located at the point (0, l). One second later, Chef observes that this endpoint is at distance d above the x-axis, i.e. the y-coordinate of this endpoint is equal to d.

Chef is curious about where the minute hand will be (specifically, its y-coordinate) after tseconds. Because t can be very large, Chef can't wait for that moment. Please help him!

Input

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first and only line of each test case contains three space-separated integers l, dand t.

Output

We can prove that for the given constraints, the y-coordinate of the end of the minute hand can always be written as a rational number p / q, where gcd(p, q) = gcd(q, 10⁹ + 7) = 1. Let's denote the modular inverse of q (it's guaranteed that the modular inverse exists and is unique) by r.

For each test case, print a single line containing one number (p · r) modulo 10⁹ + 7.

Constraints

• 1 ≤ T ≤ 10⁵
• 1 ≤ d < l ≤ 10⁹
• 1 ≤ t ≤ 10¹⁸

Subtasks

Subtask #1 (5 points): t ≤ 3

Subtask #2 (15 points): t is a power of 2, i.e. t = 2^p for some p ≥ 0

Subtask #3 (40 points): sum of t over all test cases ≤ 10⁶

Subtask #4 (40 points): original constraints

Example

Input:

3

4 2 1

4 2 2

4 2 3

Output:

2

1000000005

1000000003

贴个代码

吃个教训，在february challenge 期间就传了代码，然后有人直接就这个代码交了，被codechef发邮件通知掉rating了，以后不敢了

#include <bits/stdc++.h>

#define mst(a,b)    memset((a),(b), sizeof a)

#define lowbit(a)   ((a)&(-a))

#define IOS         ios::sync_with_stdio(0);cin.tie(0);

using namespace std;

typedef long long ll;

const int mod=1e9+;

const int maxn=1e6+;

const ll INF = 1LL<<;

const int N=;

ll qpow(ll a,ll b){

    ll ret=;

    while(b){

        if(b&)ret=ret*a%mod;

        b>>=;a=a*a%mod;

    }

    return ret;

}

struct matrix{

    ll mat[N][N];

    matrix operator*(const matrix&m)const{

        matrix tmp;

        for(int i=;i<N;++i){

            for(int j=;j<N;++j){

                tmp.mat[i][j]=;

                for(int k=;k<N;++k){

                    tmp.mat[i][j]+=mat[i][k]*m.mat[k][j]%mod;

                    tmp.mat[i][j]%=mod;

                }

            }

        }

        return tmp;

    }

};

void solve(ll d,ll l,ll t,ll&a,ll&b){

    ll gg=__gcd(d,l);d/=gg,l/=gg;l%=mod,d%=mod;

    b=qpow(l,t);--t;

    matrix m,ans;

    mst(m.mat,);mst(ans.mat,);

    for(int i=;i<N;++i)ans.mat[i][i]=;

    m.mat[][]=*d%mod;m.mat[][]=-(l*l%mod);

    m.mat[][]=;

    while(t){

        if(t&)ans=ans*m;

        t>>=;

        m=m*m;

    }

    a=(ans.mat[][]*d%mod+ans.mat[][]%mod)%mod;

    a=(a+mod)%mod;

}

int main(){

#ifdef local

freopen("in.txt","r",stdin);

//freopen("out.txt","w",stdout);

#endif

    int t;scanf("%d",&t);

    while(t--){

        ll d,l,t;scanf("%lld%lld%lld",&l,&d,&t);

        ll a,b;solve(d,l,t,a,b);

//        cout<<a<<" "<<b<<endl;

        printf("%lld\n",l*a%mod*qpow(b,mod-)%mod);

    }

    return ;

}

搞了好久，一直在想怎么用分数表示一个实数，是自己太傻逼了

用极坐标 (l，ρ)表示点，那么y就等于l*cosρ，题目给你的一秒转角α的cos值是d/l，因此只要求出t秒转过角度的cos值答案就出来啦

所以怎么求cos(tα)嘞？

由于cos(A+B)=cosAcosB-sinAsinB

　　cos(A-B)=cosAcosB+sinAsinB

两式相加得cos(A+B)+cos(A-B)=2cosAcosB

所以得到递推式   cos((t+1)α) = 2*cos(tα)cosα - cos((t-1)α）

用矩阵快速幂求出tα的cos值

怎么保证这个分数分子分母是互质的呢，因为递推式里是有分数相减的

先把d和l先除一个gcd(d,l)这样就可以先保证 d，l互质

然后因为分母一直是l的k次方，分子会是d的倍数减去l²的倍数

因为分子分母一开始互质，反证法可以证明分子分母在递推后依旧互质,所以可以大胆取模

得到cos(tα)的分数形式  a/b后，ans就是   l*a*inv(b)=l*a*pow(b,mod-2)