题目描述

对于$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$，保证除法时逆元一定存在。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。