AT_abc429_g [ABC429G] Sum of Pow of Mod of Linear

整数 $ N,M,A,B,X,R $ が与えられます。 $ \displaystyle \sum_{k=0}^{N-1} X^{(Ak+B) \bmod M} $ を $ R $ で割ったあまりを求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケース $ \text{case}_i $ は以下の形式で与えられる。 > $ N $ $ M $ $ A $ $ B $ $ X $ $ R $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについて、 $ \displaystyle \sum_{k=0}^{N-1} X^{(Ak+B) \bmod M} $ を $ R $ で割ったあまりを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて考えます。 - $ k=0 $ のとき： $ \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 0+1) \bmod 5}=2^1=2 $ です。 - $ k=1 $ のとき： $ \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 1+1) \bmod 5}=2^3=8 $ です。 - $ k=2 $ のとき： $ \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 2+1) \bmod 5}=2^0=1 $ です。 - $ k=3 $ のとき： $ \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 3+1) \bmod 5}=2^2=4 $ です。 以上より、求める値は $ 2+8+1+4 $ を $ 1000000000 $ で割ったあまりである $ 15 $ です。したがって、 $ 1 $ 行目には $ 15 $ を出力してください。 ### Constraints - $ 1\le T\le 100 $ - $ 1\le N,M,R\le 10^9 $ - $ 0\le A,B < M $ - $ 1\le X < R $ - 入力される値は全て整数