不按套路的最终boss

其实前面那么多水题都是为了留时间给大家做这道题

在游戏世界混了段日子的QwQ已经有一套不错的装备准备去打第二只Boos-Fibonacci求和

只见QwQ手起刀落，Fibonacci求和竟然被他秒杀了（没错他其实只是熟练地开起了隐藏外挂）

QwQ心想：小样，你有种跑啊，你再跑跑给我看看，老子一刀把你秒了，看你怎么跑
然而正当QwQ得意洋洋时,最终Boss-广义Fibonacci求和究极体 直接降临了，QwQ心中暗骂到这怎么跟网络小说里的套路不一样，哪有刚入新手村不久就打最终boss的。可是广义Fibonacci求和究极体并不管那么多，只见他直接攻向了QwQ

广义Fibonacci求和究极体 心想：你当我傻啊，你才几天就这么吊，再这样下去，不出一月我也危险，我怎么能再继续派小弟送经验给你呢？

为了能渡过难关，QwQ立即再次开启外挂召集所有最聪明的ACMER,作为其中之一，你能帮住他打败最终Boss-广义Fibonacci求和究极体吗？

（为了降低难度这里给出一些提示 当 a=1,b=1,F1=1,F2=2,k=3时满足下面的矩阵（是男人就不要看提示）

矩阵.png

）

有多组测试数据.第一行包含一个整数T代表数据的组数.，每组数据包含上文提到的7个整数按顺序分别是 f1, f2, a, b, k, n, m，其中  0 < f1, f2, a, b, n, m < 1000 000 000, 且 0 ≤ k < 50.

对于每组数据仅输出一行代表S(n,k) %m.结果

3
1 1 1 1 1 2 100000
1 1 1 1 1 3 100000
1 1 1 1 1 4 100000

2
4
7