Будьте эффективными
Рассмотрим целочисленную последовательность, состоящую из 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).
Выходные данные
Для каждого теста в отдельной строке вывести его номер и требуемый результат.