AT_abc402_g [ABC402G] Sum of Prod of Mod of Linear

整数 $ N,M,A,B_1,B_2 $ が与えられます。 $ \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 $ を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ ただし、 $ \text{case}_i $ は $ i $ 個目のテストケースを表す。 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ A $ $ B_1 $ $ B_2 $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースの答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 - $ k=0 $ のとき： $ \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=1,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=4 $ です。 - $ k=1 $ のとき： $ \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=3,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=6 $ です。 - $ k=2 $ のとき： $ \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=5,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=1 $ です。 - $ k=3 $ のとき： $ \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=0,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=3 $ です。 よって、求める値は $ 1\times 4+3\times 6+5\times 1+0\times 3=27 $ です。したがって、 $ 1 $ 行目には $ 27 $ を出力してください。 ### 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 $ - 入力される値は全て整数