Арифметична прогресія#11538
Вам задано арифметичну прогресію, що складається з елементів, де -й елемент визначається як a_i = (a + b \cdot (i - 1)) \bmod m.
Ваше завдання — обчислити суму цієї арифметичної прогресії \sum_{i=1}^n a_i для заданих значень , , і .
Перший рядок містить одне ціле число t~(1 \le t \le 10^5), яке вказує на кількість тестових прикладів.
У наступних рядках наведено по чотири цілі числа , , і b~(1\le n \le 10^9, 2 \le m \le 10^9 + 7, 0 \le a, b < m), що описують арифметичну прогресію.
Для кожного тестового прикладу виведіть одне число в окремому рядку — суму елементів арифметичної прогресії.
Приклад 1