"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

enter image description here

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 i^th death eater is denoted as S_i. First death eater is having strength A (i.e. S₁ = A) and second death eater is having strength B (i.e. S₂ = B). Voldemort observed that strength of i^th death eater can be represented in the form of following relation :

S_i = S_i-1 - S_i-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 10⁹+7.

Constraints

1 ≤ T ≤ 100
1 ≤ A, B, K ≤ 10¹⁸
3 ≤ N ≤ 10¹⁸