problem
Xinlv很久以前就在纸上写了一些序列，它们可能是算术序列或几何序列。这些数字现在还不是很清楚，每个序列的前三个数字都是可识别的。Xinlv想知道这些顺序中的一些数字，他需要您的帮助。
Input
第一行包含一个整数N，表示存在N个序列。接下来的N行中的每行包含四个整数。前三个表示序列的前三个数字，最后一个是K，表示我们想知道序列的第K个数字。
您可以假设0 <K <= 10 ^ 9，其他三个数字在[0，2 ^ 63）范围内。序列的所有数字都是整数。并且序列是不递减的。
Output
每个测试用例输出一行，即，第K个数字模块（％）200907。
Sample Input
2
1 2 3 5
1 2 4 5
Sample Output
5
16
code
#include<iostream>
using namespace std;
const int mod=200907;
long long fastPow(long long a,long long n){//快速幂运算 long long res=1;long long base=a;while(n){if(n&1){res=(res*base)%mod;}base=(base*base)%mod;n=n>>1;}return res;
}
int main(){int t;cin>>t;//t表示组数 long long a,b,c,k; while(t--){cin>>a>>b>>c>>k;//输入四个数 if(b-a+b==c){//算术运算 等差数列 cout<<(a%mod+(k-1)%mod*(b-a)%mod)%mod<<endl;}else{//几何运算 等比数列long long m=b/a;cout<<(fastPow(m,k-1)*(a%mod))%mod<<endl; }}return 0;
}