AT_abc402_g [ABC402G] Sum of Prod of Mod of Linear

You are given integers $ N,M,A,B_1,B_2 $ . Find $ \displaystyle\sum_{k=0}^{N-1}\left\lbrace (Ak+B_1)\ \text{mod}\ M \right\rbrace\left\lbrace (Ak+B_2)\ \text{mod}\ M \right\rbrace $ . There are $ T $ test cases; solve each one.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Here, $ \text{case}_i $ denotes the $ i $ -th test case. Each test case is given in the following format: > $ N $ $ M $ $ A $ $ B_1 $ $ B_2 $

Print $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 Consider the first test case. - When $ k=0 $ : $ \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=1,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=4 $ . - When $ k=1 $ : $ \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=3,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=6 $ . - When $ k=2 $ : $ \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=5,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=1 $ . - When $ k=3 $ : $ \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=0,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=3 $ . Hence, the required value is $ 1\times 4+3\times 6+5\times 1+0\times 3=27 $ . Thus, print $ 27 $ on the first line. ### Constraints - $ 1\le T\le 10^5 $ - $ 1\le N\le 10^6 $ - $ 1\le M\le 10^6 $ - $ 0\le A,B_1,B_2 < M $ - All input values are integers.