eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Будьте ефективними

Будьте ефективними

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Розглянемо цілочисельну послідовність, що складається з 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 (0a, b, c1000, 0 < m, n10000).

Вихідні дані

Для кожного тесту в окремому рядку вивести його номер та потрібний результат.

Приклад

Вхідні дані #1
2
2 1 2 4 4
923 278 195 8685 793
Вихідні дані #1
Case 1: 2
Case 2: 34