Arithmetic progression#11538
You are given an arithmetic progression consisting of elements, where the -th element a_i = (a + b \cdot (i - 1)) \bmod m.
Your task is to calculate the sum of the arithmetic progression \sum_{i=1}^n a_i given , , and .
The first line contains one integer t~(1 \le t \le 10^5) — the number of test cases.
The next lines contain four integers , , and b~(1\le n \le 10^9, 2 \le m \le 10^9 + 7, 0 \le a, b < m) — description of arithmetic progression.
For each test example, print on a separate line a single number — the sum of the elements of the arithmetic progression.
Example 1