Periodik nöqtələr#1820

Periodik nöqtələr

20 saniyə

256 meqabayt

Çox asan

Dinamik sistemlərdə sabit nöqtələrin və dövri orbitlərin sayını hesablamaq müxtəlif tədqiqat sahələrində maraq doğuran bir sualdır. Lakin, hətta sadə modellərdə belə dinamikləri təsvir etmək çox mürəkkəb ola bilər. Bu tapşırıqda sizdən $f$ parça xətti xəritəsinin $[0, m]$ real intervalını özünə xəritələndirən dövri nöqtələrin sayını hesablamaq tələb olunur. Yəni, verilmiş $f$ xəritəsi üçün: $[0, m] \to [0, m]$ [0, m] \rightarrow [0, m] siz $f^{n} (x) = x$ f^n(x) = x tənliyinin həllərinin sayını $x \in [0, m]$ x \in [0, m] üçün hesablamaq məcburiyyətindəsiniz, burada $f^{n}$ f^n funksiyanın $n$ dəfə təkrarlanmasının nəticəsidir, yəni

burada $\circ$ xəritələrin tərkibi üçün dayanır, $(g h) (x) = g (h (x))$ (gh)(x) = g(h(x)).

Bu tapşırıqda işləməli olduğunuz xəritələr aşağıdakı xüsusiyyətlərə malikdir:

$m$ müsbət tam ədəd olacaq və $[0, m]$ aralığında olan hər tam ədəd üçün $f (k)$ də $[0, m]$ aralığında tam ədəd olacaq, yəni hər bir $k \in {0, 1, \dots, m}$ k \in \{0, 1, \ldots, m\} üçün $f (k) \in {0, 1, \dots, m}$ f(k) \in \{0, 1, \ldots, m\}.
Hər $k \in {0, 1, \dots, m - 1}$ k \in \{0, 1, \ldots, m-1\} üçün $f$ xəritəsi $[k, k + 1]$ [k, k+1] aralığında xəttidir. Yəni, hər bir $x \in [k, k + 1]$ x \in [k, k+1] üçün $f (x) = (k + 1 - x) f (k) + (x - k) f (k + 1)$ f(x) = (k + 1 - x) f(k) + (x - k) f(k + 1), yəni onun qrafiki bu aralıqda düz xətt segmentidir.

Şəkil 1: Nümunədəki üçüncü xəritənin qrafiki, $f_{3}$ f_3 (solda) və onun kvadratı, $f_{3}^{2}$ f_3^2 (sağda).

Çoxlu dövri nöqtə ola biləcəyi üçün cavabı tam ədədə görə modulla verin.

Giriş

Giriş birdən çox test halından ibarətdir, sətirlər bir boş sətirlə ayrılıb. Hər test halı tam ədəd $m$ ( $1 \leq m \leq 80$ 1 \leq m \leq 80) olan bir sətrlə başlayır. Növbəti sətirdə xəritə $f$ təsvir edilir; burada $m + 1$ m+1 tam ədəd $f (0), f (1), \dots, f (m)$ f(0), f(1), \ldots, f(m) verilir, hər biri $0$ və $m$ daxil olmaqla aralıqdadır. Test halı iki tam ədəd olan bir sətrlə bitir, boşluqla ayrılıb: $n$ ( $1 \leq n \leq 5000$ 1 \leq n \leq 5\ 000) və nəticənin hesablamaq üçün modulu $mod$ ( $2 \leq mod \leq 10000$ 2 \leq \text{mod} \leq 10\ 000).

Giriş **'0'** sətri ilə bitir.

Çıxış

Hər test üçün $[0, m]$ aralığında $f^{n} (x) = x$ f^n(x) = x tənliyinin həllərinin sayını $mod$ modula görə çıxarın. Əgər sonsuz sayda həll varsa, **'Infinity'** yazın.

Nümunələr

Nümunə 1