One night, Sheldon was visited by Spock in his dream. Spock told Sheldon about a special number series - (called the Spock Series, as it was discoverd by Spock). Spock says that nth number of the Spock Series is given as : f(n) = a*f(n-1) + b*f(n-i) + c*f(n-7) where a, b, c and i are integers. Spock says that i is always less than 6. Also Spock tells him that values of f(1)...f(7) are all 1. But Spock refuses to tell him the value of the nth number of Spock series.

So Sheldon decides to work out these numbers on his own.

Input :

First line is an integer T - the number of test cases. Each test case is described below :

Each test case starts with a line containing 4 space seperated integers - a, b, c, i. Next line contains an integer n - the nth term to be found


Output :

Corresponding to each n, print the nth number mod 1000000007 corresponsing to that Spock series in a new line.

Constraints :

0 < T < = 2100
1 < = a, b, c < = 600
1 < i < 6
1 < n < 1500

Input:
1
1 1 1 2
8

Output:
3

Explanation:
given formula is f(n)=f(n-1)+f(n-2)+f(n-7) and f(1), f(2)...f(7) = 1
so f(8)=f(1)+f(6)+f(7) = 3