Задачи
Очень просто
Очень просто
Алиса и Боб хотят секретно передавать сообщения друг другу, и для этого они разработали генератор случайных чисел (ГСЧ), который инициализируется тремя целыми числами: a0
, a1
и n. Первыми элементами ГСЧ являются a0
иa1
, следующие элементы строятся так: ai+2
= (ai+1
* ai+1
+ ai
* ai
) mod n, i = 0, 1, ...
Алиса и Боб будут использовать ГСЧ в схеме передачи данных, как показано на рисунке.
Для создания ГСЧ они хотят написать процедуру, вычисляющую для заданного k значение ak
. Помогите им!
Входные данные
В первой строке даны четыре натуральных числа n, a0
, a1
и k, где 0 ≤ ak
, ak
< n ≤ 200, и 0 ≤ k ≤ 109
.
Выходные данные
Выведите одно число ak
.
Входные данные #1
10 0 1 4
Выходные данные #1
5
Входные данные #2
10 2 4 5
Выходные данные #2
2
Входные данные #3
200 133 166 233266300
Выходные данные #3
146