1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #define m 200907 5  6 using namespace std; 7  8 __int64 fun(__int64 j,__int64 k) 9 {10     __int64 s=1;11     while (k)12     {13         if (k%2==1)14             s=s*j%m;15         j=(j*j)%m;16         k/=2;17     }18     return s;19 }20 int main ()21 {22     __int64 t,a,b,c,n,s;23     cin>>t;24     while (t--)25     {26         cin>>a>>b>>c>>n;27         if (b-a==c-b)28         {29             int d=b-a;30             s=(a+(n-1)*d)%m;31         }32         else33         {34             int q=b/a;35             s=(a*fun(q,n-1))%m;36         }37         printf ("%I64d\n",s);38     }39     return 0;40 }