AT_abc429_g [ABC429G] Sum of Pow of Mod of Linear

You are given integers $ N,M,A,B,X,R $ . Find the remainder when $ \displaystyle \sum_{k=0}^{N-1} X^{(Ak+B) \bmod M} $ is divided by $ R $ . You are given $ T $ test cases, so find the answer for each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case $ \text{case}_i $ is given in the following format: > $ N $ $ M $ $ A $ $ B $ $ X $ $ R $

Print $ T $ lines. On the $ i $ -th line, print the remainder when $ \displaystyle \sum_{k=0}^{N-1} X^{(Ak+B) \bmod M} $ is divided by $ R $ for the $ i $ -th test case.

### Sample Explanation 1 Consider the first test case. - When $ k=0 $ : $ \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 0+1) \bmod 5}=2^1=2 $ . - When $ k=1 $ : $ \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 1+1) \bmod 5}=2^3=8 $ . - When $ k=2 $ : $ \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 2+1) \bmod 5}=2^0=1 $ . - When $ k=3 $ : $ \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 3+1) \bmod 5}=2^2=4 $ . From the above, the desired value is the remainder when $ 2+8+1+4 $ is divided by $ 1000000000 $ , which is $ 15 $ . Therefore, print $ 15 $ on the $ 1 $ st line. ### Constraints - $ 1\le T\le 100 $ - $ 1\le N,M,R\le 10^9 $ - $ 0\le A,B < M $ - $ 1\le X < R $ - All input values are integers.