Migrated from Lutece 3011 暗淡星

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

"爱情，长生种和短生种之间，星系这端和星系那端，最后，都不会有好结局的，尽早放弃吧，于你于她，都好。"

"为什么？爱情不应该被这些东西所束缚！"

"唉，没经历过黑发人送白发人，没经历过你的一秒她的一生，你是不会理解的。"

"不，我一定会打破寿命论和时空论的！我一定要和她在一起！"

...

花白头发的博士叹了口气，摇了摇头看着一位年轻气盛的黑发小伙走开，仿佛看着当年的自己。

几百年后，老博士已经不在，小伙也变成了老头，他的爱人或许早已离世，可是他眼中的那股坚定，仍未消散。

"时间线，不顾一切地将我们向前推；重力空间，死死的压着我们；物理规则就是如此，但是，规则，就是用来打破的！"

因苍老而微微发抖的手仍在光写板上计算着，那位原来的年轻人，仍然在寻找着突破一切的答案。

"就差一点，就差一点，只需求出这个，呃，啊！"

哐当，笔掉在金属地板上发出响亮的声音，那个苍老的身影也最终倒下，瞳孔已经放大，但充满着不甘心。

此时，一道身影由虚凝实，你从虚数空间出来，来到这个写满公式的光写板前，发现老者只差最后一步，就能脱离时间空间的限制了，你决定帮他完成这个持续数百年的努力。

现在，两条相邻时间线的奇点分布可以由两个线性递推式表示，第一条的第 $i$ 个奇点权重为 $a[i]=A\times a[i-1] + B$，第二条的第 $i$ 个奇点权重为 $b[i]=C\times b[i-1] + D$，然后对于其交叉干涉空间重力因子可以表示为 $c[i]=a[i]\times b[i]$，脱离时空限制，从当前，假设为 $1$ 号时间点，然后到目标 $n$ 号时间点的任意指定空间所需要的撕裂算子在能量数值上为

$E=\sum_{i=1}^n c[i]$

现在，你知道改变老者命运的时空坐标，也就是目标时间点的编号 $n$，还有两条相邻时间线的时间常数观测结果 $A,B,C,D$，然后和当前初始时间奇点权重 $a[1], b[1]$，你需要快速知道所需 $E$ 的大小，这样你就能在当前时空仍未发生波动变化情况下，将结果在老者死前告诉他，从而改变他的命运。

由于时间线很多，你需要至少改变 $T$ 条时间线上的老者命运才能完全扭转结局，否则命运的齿轮会将其变回原来结局。

对于每一条时间线，你知道 $n,A,B,C,D,a[1],b[1]$，你只需快速计算出对应的 $E$ 即可。所有时间线的 $E$ 要在$1s$ 内计算完成，你才能成功。

Input

第一行输入一个整数 $T$，接下来 $T$ 行，每行 $7$ 个数字 $a[1],b[1],A,B,C,D,n$ 含义如上。

Output

输出 $T$ 行，每行一个整数，表示对应 $E$ 在模 $998244353$ 意义下的值。

Samples

3
1 2 3 4 5 6 3
1 3 5 7 9 11 100 
1 1 4 5 1 4 1919810

2264
407338641
129224030

Constraints

$1\leq T\leq 10^5,1\leq n\leq 10^9,1\leq a[1],b[1],A,B,C,D< 998244353$

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming