Дуже просто
Дуже проста
Обмеження на час виконання 1 секунда
Обмеження на використання пам'яті 128 мегабайтів
Аліса та Боб хочуть секретно передавати повідомлення один одному, і для цього вони розробили генератор випалкових чисел (ГВЧ), який ініціалізується трьома цілими числами: 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]
.
Приклади
Вхідні дані #1
Відповідь #1
Вхідні дані #2
Відповідь #2
Вхідні дані #3
Відповідь #3
Відправки 88
Коефіцієнт прийняття 35%