时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
终于活成了自己讨厌的样子。
听说多听电音能加快程序运行的速度。
定义一个数列，告诉你a
0,a
1,m
0,m
1,c，定义a
n=m
0a
n-1+m
1a
n-2+c对所有n≥ 2。
求
%20%5Cbmod%20M)
输入描述:
第一行一个整数T(1≤ T≤ 1000)，表示数据组数。
每组数据一行7个整数a0,a1,m0,m1,c,M,k，保证1≤ M≤ 1018,0≤ a0,a1,m0,m1,c< M, 2≤ k≤ 106，保证M为奇数。
保证
。
输出描述:
对于每组数据，输出一行表示答案。
示例1
输入
复制
1
1 1 1 1 0 1000000007 10