BSNY 在學(xué)等差數(shù)列和等比數(shù)列，當(dāng)已知前三項(xiàng)時(shí)，就可以知道是等差數(shù)列還是等比數(shù)列?，F(xiàn)在給你序列的前三項(xiàng)，這個(gè)序列要么是等差序列，要么是等比序列，你能求出第 k 項(xiàng)的值嗎。 如果第 k 項(xiàng)的值太大，對(duì) 200907 取模。

第一行一個(gè)整數(shù) T，表示有 T 組測(cè)試數(shù)據(jù)；

對(duì)于每組測(cè)試數(shù)據(jù)，輸入前三項(xiàng) a,b,c，然后輸入 k。

對(duì)于每組數(shù)據(jù)輸出第 k 項(xiàng)的值，對(duì) 200907 取模。

樣例說(shuō)明：

第一組是等差序列，第二組是等比數(shù)列。

數(shù)據(jù)范圍與提示：

對(duì)于全部數(shù)據(jù)，1≤T≤100,1≤a≤b≤c≤10⁹,1≤k≤10⁹ 。

信息學(xué)一本通 數(shù)學(xué)