最近又开始做ACM了。原因是，我在学校里面找了份兼职，做ACM兴趣班的助教。
任务是给大一的新生讲一些ACM的入门知识。
虽然讲的东西很基础很简单，但我觉得他们的潜力巨大，很快就能达到跟我一样的水平。。
所以我自己也得补下课啦。
这次我下决心，坚决不做一道水题！
我放弃了原来在POJ账号，转战HOJ，因为这样我才不会为了题目数量而刷水题。
我觉得以前真的很傻逼，老是挑着做一些自己已经会了的题目，还总是抱怨自己的水平一直没提高。
整天刷水题，水平他妈的能提高么。
人都是很懒的，懒得动脑子，只是享受敲完一道水题后ac的感觉，还很有成就感。
但这样子有什么用，遇到难题的时候，始终还是想不出来，还以为是自己脑子不好使。
实际上不是的，只要克服惰性，多思考问题，每个人的脑子都是很好使的。
我挑战的第一道难题，呵呵，对我来说比较难的题，就是这道。
想了一下发现了这个规律：
(A*B)%M = ((A%M)*(B%M))%M
演算一下就可以得出这个的。
对与输入中的一个数字，可以分别计算出：
A%M
A^2 %M
A^4 %M
...
然后再相乘取模就行了。
这样二分一下，就很好办了。
这是我自己克服了懒惰动了脑子想出来的！我他妈的很自豪！
#include <stdio.h>
__int64 N, K, A, B, C, d, i, n, ans;
#define M 200907
int main()
{
scanf("%I64d", &N);
while (N--) {
scanf("%I64d%I64d%I64d%I64d", &A, &B, &C, &K);
if (B - A == C - B) {
ans = ((A%M) + (((K-1)%M)*((B-A)%M)%M))%M;
} else {
d = (B/A)%M;
n = K - 1;
ans = A%M;
for (i = 0; (1LL << i) <= n; i++) {
if (n & (1LL << i))
ans = (ans*d)%M;
d = (d*d)%M;
}
}
printf("%I64d\n", ans);
}
return 0;
}