Link - https://www.hackerearth.com/challenges/hiring/zauba-campus-hiring-challenge19/

Sequential Terms

You are required to determine the n_{th} 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 \times f(n - 1) + b \times f(n-2) + c \times f(n - 3) + g(n)

where g(n) = n \times n \times (n + 1)

**Note** Since n_{th} term would be too large, therefore print the value as f(n) (mod (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) \% (10^9 + 7) that represents the n_{th} term of the sequence in a new line

**Constraints**

1 \leq t \leq 50

1\leq p,q,r,a,b,c,n \leq 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

**Explanation**

In Test case 4 :

For the given values of p,q,r,a,b,c

f[0] = 1

f[1] = 2

f[2] = 3

f[3] = 1 \times f[2] + 1 \times f[1] + 1 \times f[0] + 3 \times 3 \times (3 + 1)

f[3] = 1+ 2 + 3 + 36

f[3] = 42

**Time Limit**

5 sec for each test file

If it was simple tribonacci series I would have solved it using companion matrix and matrix exponential method. But how to solve the above problem??