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