Solving a relation
75% Success16 Attempts50 Points5s Time Limit256MB Memory1024 KB Max Code

You are required to determine the \(n^{th}\) terms of the following relation:

\(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)\)

Since the \(n^{th}\) term can be too large, therefore you are required to print \(f(n)\ modulo\ (1000000007)\).

Input format

  • First line: \(t\) denoting the number of test cases
  • Each of the \(t\) line: Seven integers \(p,\ q,\ r,\ a,\ b,\ c,\ n\)

Output format
For each test case, print \(f(n) modulo(1000000007)\) 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}\)

Examples
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
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*f[2] + 1*f[1] + 1*f[0] + 3*3*(3+1)
f[3]= 1 + 2 + 3 + 36
f[3]= 42

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...
Results