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