给你一个递推公式：
f(x)=a*f(x-2)+b*f(x-1)+c
并给你f(1),f(2)的值，请求出f(n)的值，由于f(n)的值可能过大，求出f(n)对1000007取模后的值。
注意:-1对3取模后等于2
递推求值
Input
第一行是一个整数T,表示测试数据的组数(T<=10000)
随后每行有六个整数，分别表示f(1),f(2),a,b,c,n的值。
其中0<=f(1),f(2)<100,-100<=a,b,c<=100,1<=n<=100000000 (10^9)
随后每行有六个整数，分别表示f(1),f(2),a,b,c,n的值。
其中0<=f(1),f(2)<100,-100<=a,b,c<=100,1<=n<=100000000 (10^9)
Output
输出f(n)对1000007取模后的值
Sample Input
2
1 1 1 1 0 5
1 1 -1 -10 -100 3
Sample Output
5
999896