Periodik nöqtələr
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] → [0, m] siz f^n(x) = x tənliyinin həllərinin sayını [0, m] intervalında hesablamaq məcburiyyətindəsiniz, burada f^n funksiyanın n dəfə təkrarlanmasının nəticəsidir, yəni
o
o
burada xəritələrin tərkibi üçün dayanır, (gh)(x) = g(h(x)).
Xoşbəxtlikdən, işləməli olduğunuz xəritələr bəzi xüsusi xüsusiyyətlərə malikdir:
m müsbət tam ədəd olacaq və f altında [0, m] hər bir tam ədədin təsviri yenidən [0, m] intervalında tam ədəd olacaq, yəni hər bir k üçün
{0, 1,..., m} bizdə f (k)
{0, 1,..., m} var.
Hər bir k üçün
{0, 1,..., m - 1}, f xəritəsi [k, k + 1] intervalında xətti olur. Bu o deməkdir ki, hər bir x üçün
[k, k + 1], onun təsviri f (x) = (k + 1 - x)f (k) + (x - k)f (k + 1) bərabərliyini təmin edir, bu isə [k, k + 1] intervalında onun qrafikinin düz xətt seqmenti olması ilə ekvivalentdir.
Şəkil 1: Nümunə girişdəki üçüncü xəritənin, f_3 (sol), və onun kvadratının, f_3^2 (sağ), qrafikləri.
Çoxlu dövri nöqtələr ola biləcəyi üçün nəticəni tam ədədə görə modula çıxmalısınız.
Giriş verilənləri
Giriş bir neçə test halından ibarətdir, boş sətirlərlə ayrılmışdır. Hər bir test halı bir sətirlə başlayır və bu sətir tam ədəd m (1 ≤ m ≤ 80) ehtiva edir. Növbəti sətir xəritəni təsvir edir f; o, m+1 tam ədədləri ehtiva edir f(0), f(1), ..., f(m), hər biri 0 və m daxil olmaqla arasında. Test halı iki tam ədəd ilə bitir, boşluqla ayrılmış, n (1 ≤ n ≤ 5 000) və nəticəni hesablamaq üçün istifadə olunan modul, "mod" (2 ≤ mod ≤ 10 000).
Giriş '0' sətiri ilə bitəcək.
Çıxış verilənləri
Hər bir hal üçün, proqramınız f^n(x) = x tənliyinin [0, m] intervalında həllərinin sayını "mod" modula görə çıxmalıdır. Əgər sonsuz sayda həllər varsa, 'Infinity' çap edin.