Периодические точки
Вычисление количества неподвижных точек и, более широко, количества периодических орбит в динамических системах — это задача, вызывающая интерес в различных областях исследований. Однако динамика может быть очень сложной даже в, казалось бы, простых моделях. В этой задаче вам предстоит вычислить количество периодических точек периода n для кусочно-линейного отображения f, которое отображает действительный интервал [0, m] в себя. То есть, дано отображение f : [0, m] → [0, m], и вам нужно найти количество решений уравнения f^n(x) = x для x в [0, m], где f^n — это результат n-кратной итерации функции f, то есть
где обозначает композицию отображений, (gh)(x) = g(h(x)).
К счастью, отображения, с которыми вы будете работать, обладают некоторыми особыми свойствами:
m — положительное целое число, и образ каждого целого числа в [0, m] под действием f также является целым числом в [0, m], то есть для каждого k в {0, 1,..., m} выполняется f(k) в {0, 1,..., m}.
Для каждого k в {0, 1,..., m - 1}, отображение f линейно на интервале [k, k + 1]. Это означает, что для каждого x в [k, k + 1], его образ удовлетворяет f(x) = (k + 1 - x)f(k) + (x - k)f(k + 1), что эквивалентно тому, что его график на [k, k + 1] является отрезком прямой.
Рисунок 1: Графики третьего отображения в примере ввода, f_3 (слева), и его квадрата, f_3^2 (справа).
Поскольку может быть много периодических точек, вам нужно будет вывести результат по модулю целого числа.
Входные данные
Ввод состоит из нескольких тестов, разделенных одной пустой строкой. Каждый тест начинается с строки, содержащей целое число m (1 ≤ m ≤ 80). Следующая строка описывает отображение f; она содержит m+1 целых чисел f(0), f(1), ..., f(m), каждое из которых находится в диапазоне от 0 до m включительно. Тест заканчивается строкой, содержащей два целых числа, разделенных пробелом, n (1 ≤ n ≤ 5 000) и модуль, используемый для вычисления результата, "mod" (2 ≤ mod ≤ 10 000).
Ввод заканчивается строкой, содержащей '0'.
Выходные данные
Для каждого случая ваша программа должна вывести количество решений уравнения f^n(x) = x в интервале [0, m] по модулю "mod". Если решений бесконечно много, выведите 'Infinity'.