递推数列

【题目描述】

对于$f(i)=\frac{af(i-1)+b}{cf(i-1)+d}\bmod p$，给定$f(0),a,b,c,d,n,p$，求$f(n)$。 有多组数据。

【输入】

第一行一个整数$t$表示数据组数。 接下来的$t$行，每行七个整数$f(0),a,b,c,d,n,p$。

【输出】

每组数据输出一行一个整数表示答案。

【输入样例】

1
54 40 11 39 -40 66 73

【输出样例】

54

【提示】

【数据规模与约定】 对于10%的数据，$t≤10，n≤100，p≤100$。 对于40%的数据，$t≤10，p≤1000$。 对于100%的数据，$1≤t≤10^4，0≤n≤10^{18}，2≤p≤10^9，0≤|f(0)|,|a|,|b|,|c|,|d|<p$，保证除法时逆元一定存在。