Алиса и Боб хотят секретно передавать сообщения друг другу, и для этого они разработали генератор случайных чисел (ГСЧ), который инициализируется тремя целыми числами: 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]
.