Будьте ефективними
Розглянемо цілочисельну послідовність, що складається з n елементів: x_0 = a,
x_i = ((x_i_{-1} * b + c ) % m) + 1 для i = 1, 2, ... n - 1
Задані числа a, b, c, m, n. Знайти кількість “послідовних підпослідовностей”, сума чисел яких ділиться на m.
Розглянемо приклад, в якому a = 2, b = 1, c = 2, m = 4, n = 4. Тоді
x_0 = 2,
x_i = (x_i_{-1} + 2) % 4 + 1, i = 1, 2, 3, 4
Звідки x_0 = 2, x_1 = 1, x_2 = 4, x_3 = 3. Послідовними підпослідовностями будуть {2}, {2 1}, {2 1 4}, {2 1 4 3}, {1}, {1 4}, {1 4 3}, {4}, {4 3} и {3}. Із перелічених 10 підпослідовностей сума лише двох ділиться на 4: {1, 4, 3} та {4}.
Вхідні дані
Перший рядок містить кількість тестів t (t < 500). Кожний наступний рядок є окремим тестом і містить п'ять цілих чисел: a, b, c, m, n (0 ≤ a, b, c ≤ 1000, 0 < m, n ≤ 10000).
Вихідні дані
Для кожного тесту в окремому рядку вивести його номер та потрібний результат.