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