41 lines
882 B
C++
41 lines
882 B
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
#define int long long
|
||
|
||
const int MOD = 200907;
|
||
|
||
// 龟速乘，快速加
|
||
int qadd(int a, int b) {
|
||
int res = 0;
|
||
while (b) {
|
||
if (b & 1) res = (res + a) % MOD;
|
||
b >>= 1;
|
||
a = (a + a) % MOD;
|
||
}
|
||
return res;
|
||
}
|
||
|
||
// 快速幂
|
||
int qmi(int a, int b) {
|
||
int res = 1;
|
||
while (b) {
|
||
if (b & 1) res = (res * a) % MOD;
|
||
b >>= 1;
|
||
a = a * a % MOD;
|
||
}
|
||
return res;
|
||
}
|
||
|
||
signed main() {
|
||
int T;
|
||
cin >> T;
|
||
while (T--) {
|
||
int a, b, c, k;
|
||
cin >> a >> b >> c >> k;
|
||
if (a + c == b + b)
|
||
cout << (qadd(b - a, k - 1) + a) % MOD << endl; // 为等差即套公式，首项+公差*（项数-1）
|
||
else
|
||
cout << qmi(b / a, k - 1) * a % MOD << endl; // 等比数列用快速幂算末项
|
||
}
|
||
}
|