**Sequential terms**

You are required to determine the nth term of the provided sequence whose relation is as follows:

f(0)=p

f(1)=q

f(2)=r

for n > 2

f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+g(n)

where g(n)=n*n*(n+1)

Note: Since the nth term would be too large, therefore print the value as f(n) modulo 10^9+7

**Input Format**

- First line: t denoting the number of test cases
- Each of the t lines: Seven integers p,q,r,a,b,c,n

**Output Format**

For each test case, print f(n)% (1000000007) that represent the nth term of the sequence in a new line.

**Constraints:**

1<= t <= 50

1<= p, q, r, a, b, c, n <= 10^18

**Sample Input**

4

1 2 3 1 1 1 0

1 2 3 1 1 1 1

1 2 3 1 1 1 2

1 2 3 1 1 1 3

**Sample output**

1

2

3

42

The straight forward approach gives me TLA, I am stuck on this problem since last 3-4 days. Help is appreciated.