Аліса та Боб хочуть секретно передавати повідомлення один одному, і для цього вони розробили генератор випалкових чисел (ГВЧ), який ініціалізується трьома цілими числами: a[0]
, a[1]
та n. Першими елементами ГВЧ є a[0]
та a[1]
, наступні елементи будуються так: a[i+2]
= (a[i+1]
* a[i+1]
+ a[i]
* a[i]
) mod n, i = 0, 1, ...
Аліса та Боб будуть використовувати ГВЧ у схемі передачі даних, як показано на рисунку.
Для створення ГВЧ вони хочуть написати процедуру, яка обчислює для заданого k значення a[k]
. Допоможіть їм!
У першому рядку задано чотири натуральних числа n, a[0]
, a[1]
та k, де 0 ≤ a[k]
, a[k]
< n ≤ 200, і 0 ≤ k ≤ 10^9
.
Виведіть одне число a[k]
.