题号：NC226821
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
已知数列
%5Cspace)
满足
%5Cspace%20%3D%20x%2C%20f(1)%3Dy%2C%20f(n)%3Daf(n-1)%2Bbf(n-2))
。
输入x,y,a,b,n， 求f(n)对
取模的结果。
输入描述:
第一行输入一个整数T，表示T组测试用例。
接下来T行，每行5个数,x,y,a,b,n
输出描述:
输出T行，每行一个答案。
示例1
输入
复制
7
0 1 1 1 0
0 1 1 1 1
0 1 1 1 2
0 1 1 1 3
0 1 1 1 4
0 1 1 1 5
3 4 5 6 3
说明
x=0, y=0时，f为斐波那契数列，前5项分别为1,1,2,3,5
最后一行可以自行计算~