题目描述

给出数列前三项a,b,c，它是等差数列或整数公比等比数列，求第k项对200907取模的结果。两类同时成立时是常数列，答案相同。

本题为一本通1615的本地训练修订版。

输入

第一行T，1≤T≤100。每组a b c k，1≤a≤b≤c≤10^9，1≤k≤10^9；保证是等差数列或公比为正整数的等比数列。

输出

每组一行0..200906的整数。

输入样例

2
1 2 3 5
1 2 4 5

输出样例

5
16

修订说明

明确等比公比是整数，避免4,6,9等后续非整数项没有通常模定义的歧义。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：明确等比公比是整数，避免4,6,9等后续非整数项没有通常模定义的歧义。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1615。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共4个测试点，非原站或官方原始数据。总分100分。