"The boy has discovered our secret, Nagini. It makes us vulnerable. We must deploy all our forces now to find him. And you, my friend, must stay close." - Voldemort
Chotu Potter is on the mission of destroying all the horcruxes of Lord Voldemort and is currently at Hogwarts to destroy the last horcrux (Ravenclaw's Diadem). Voldemort wants to stop Chotu Potter by attacking Hogwarts with his army. Now using Dark Magic Voldemort creates a large army of N death eaters. Strength of ith death eater is denoted as Si. First death eater is having strength A (i.e. S1 = A) and second death eater is having strength B (i.e. S2 = B). Voldemort observed that strength of ith death eater can be represented in the form of following relation :
Si = Si-1 - Si-2 + K*i ∀ i ≥ 3
Chotu Potter somehow comes to know the above relation and wants to find out the total strength of Voldemort's army. Help Chotu in his task.
Input
First line contains an integer T, denoting total number of test cases.
Next T lines contain four integers separated by a single space denoting A, B, K and N respectively.
Output
For each test case print strength of Voldemort's Army. Since answer can be very large so print answer modulo 109+7.
Constraints
1 ≤ T ≤ 100
1 ≤ A, B, K ≤ 1018
3 ≤ N ≤ 1018
In 2nd test case :
S1 = 6
S2 = 2
S3 = 2 - 6 + 10 * 3 = 26
S4 = 26 - 2 + 10 * 4 = 64
S5 = 64 - 26 + 10 * 5 = 88
Hence total strength of Voldemort's army is 6 + 2 + 26 + 64 + 88 = 186
