3293. A Sequence of Numbers

import java.io.*;

public class Main {

    /**
     * http://acm.tju.edu.cn/toj/showp3293.html
     * @author hunglee
     */
    public static void main(String[] args) throws IOException {
        
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(
                new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(System.out);
        
        long N, a, b, c, d, k, i, m = 200907, n, res;
        
        in.nextToken();
        N = (long) in.nval;
        while (N-- > 0) {
            in.nextToken();
            a = (long) in.nval;
            in.nextToken();
            b = (long) in.nval;
            in.nextToken();
            c = (long) in.nval;
            in.nextToken();
            k = (long) in.nval;
            if (c - b == b - a) {
                res = ((a % m) + (((k - 1) % m) * 
                        ((b - a) % m) % m)) % m;
            } else {
                d = (b / a) % m;
                n = k - 1;
                res = a % m;
                for (i = 0; (1l << i) <= n; ++i) {
                    if ((n & (1l << i)) != 0)
                        res = (res * d) % m;
                    d = (d * d) % m;
                }
            }
            out.println(res);
        }
        out.flush();
    }

}