Періодичні точки#1820

Періодичні точки

20 секунд

256 мегабайтів

Дуже легка

Обчислення кількості фіксованих точок і, загалом, кількості періодичних орбіт у динамічній системі є питанням, яке становить інтерес для багатьох галузей досліджень. Однак динаміка може бути дуже складною навіть у, здавалося б, простих моделях. У цьому завданні вам належить обчислити кількість періодичних точок періоду $n$ кусково-лінійного відображення $f$ , що відображає дійсний інтервал $[0, m]$ у себе. Тобто, якщо дано відображення $f : [0, m] \to [0, m]$ f : [0, m] \rightarrow [0, m], необхідно визначити кількість розв'язків рівняння $f^{n} (x) = x$ f^n(x) = x для $x \in [0, m]$ x \in [0, m], де $f^{n}$ f^n означає $n$ -кратне застосування функції $f$ , тобто

де $\circ$ позначає композицію відображень, $(g h) (x) = g (h (x))$ (gh)(x) = g(h(x)).

На щастя, відображення у цій задачі мають такі властивості:

$m$ — це додатне ціле число, і для кожного цілого $k \in {0, 1, \dots, m}$ k \in \{0, 1, \ldots, m\} $f (k)$ — ціле число в $[0, m]$ ; тобто $f (k) \in {0, 1, \dots, m}$ f(k) \in \{0, 1, \ldots, m\}.
Для кожного $k \in {0, 1, \dots, m - 1}$ k \in \{0, 1, \ldots, m-1\} відображення $f$ лінійне на інтервалі $[k, k + 1]$ [k, k+1]. Це означає, що для будь-якого $x \in [k, k + 1]$ x \in [k, k+1] виконується $f (x) = (k + 1 - x) f (k) + (x - k) f (k + 1)$ f(x) = (k + 1 - x) f(k) + (x - k) f(k+1); тобто його графік на $[k, k + 1]$ [k, k+1] — відрізок прямої.

Рисунок 1: Графіки третього відображення з прикладу, $f_{3}$ f_3 (ліворуч), та його квадрата, $f_{3}^{2}$ f_3^2 (праворуч).

Оскільки періодичних точок може бути багато, виводьте відповідь за модулем числа.

Вхідні дані

Ввід складається з декількох тестових випадків, розділених одним порожнім рядком. Кожен тестовий випадок починається з рядка з цілим числом $m$ ( $1 \leq m \leq 80$ 1 \leq m \leq 80). Наступний рядок описує відображення $f$ : в ньому $m + 1$ m+1 цілих чисел $f (0), f (1), \dots, f (m)$ f(0), f(1), \ldots, f(m), кожне з яких знаходиться в діапазоні від $0$ до $m$ включно. Тест закінчується рядком з двома цілими числами через пробіл: $n$ ( $1 \leq n \leq 5000$ 1 \leq n \leq 5\ 000) та модуль для відповіді $mod$ ( $2 \leq mod \leq 10000$ 2 \leq \text{mod} \leq 10\ 000).

Ввід завершується рядком, що містить '0'.

Вихідні дані

Для кожного тесту виведіть кількість розв'язків рівняння $f^{n} (x) = x$ f^n(x) = x на інтервалі $[0, m]$ за модулем $mod$ . Якщо розв'язків нескінченно багато, виведіть 'Infinity'.

Приклади

Приклад 1