Link - Zauba Campus Hiring Challenge'19 - 2019 Batch
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??