Çox sadədir

Alisa və Bob bir-birlərinə gizli mesajlar göndərmək istəyirlər və bunun üçün üç tam ədədlə: a[0], a[1] və n ilə başlanğıc verilən təsadüfi ədədlər generatoru (TƏG) hazırlayıblar. TƏG-nin ilk elementləri a[0] və a[1]-dir, növbəti elementlər isə belə qurulur: a[i+2] = (a[i+1] * a[i+1] + a[i] * a[i]) mod n, burada i = 0, 1, ...

Alisa və Bob TƏG-ni məlumat ötürmə sxemində istifadə edəcəklər, şəkildə göstərildiyi kimi.

TƏG yaratmaq üçün onlar verilmiş k üçün a[k] dəyərini hesablayan bir prosedur yazmaq istəyirlər. Onlara kömək edin!

Giriş məlumatları

Birinci sətirdə dörd natural ədəd n, a[0], a[1] və k verilir, burada 0 ≤ a[k], a[k] < n ≤ 200, və 0 ≤ k ≤ 10^9.

Çıxış məlumatları

Bir ədəd a[k] çap edin.

Nümunələr