Задача P. Признак четырех ≡

Условие

 — Итак, господа, в соответствии с завещанием, для подтверждения прав на сокровища Агры четверо претендентов должны назвать кодовое число. Насколько я понимаю, у каждого из вас есть какая-то информация об этом числе, его признак. Я могу дать Вам время посовещаться, но предупреждаю, что у Вас будет единственная попытка. В случае, если Ваше число не совпадёт с моим, сокровище поступает в полное распоряжение Короны.

Такими словами завершил свое торжественное заявление глава адвокатской конторы "Lloyds and Sons". Мы переглянулись. Пришло время открыть карты. Каждый понимал, чем чревата ошибка.

 — Мне известно, что при делении этого числа на a получится остаток x,  — первой нарушила молчание Мэри Морстен.

 — Мы знаем, что при делении этого числа на b получится остаток y, а при делении на c получится остаток z  — отозвался один из братьев Шолто. Признаюсь, я до сих пор путал, кто из них кто.

 — Подходящих чисел всё ещё бесконечно много. Ну же, Джонатан Смолл, ваш черед. Или сокровище получают все, или никто, назад пути нет,  — в голосе Холмса послышались стальные нотки.

 — Ладно, ваша взяла. Из всех подходящих натуральных чисел нужно взять n-е по счету,  — разомкнул уста бывший каторжник.

 — Итак, господа, Вы готовы?  — спросил мистер Ллойд.

Мы растеряно молчали. В конце концов все взоры устремились на Холмса. Сможет ли он и на этот раз блеснуть своим интеллектом?

Формат входных данных

Первая строка входного файла содержит натуральное число a и неотрицательное целое число x. Во второй и третьей строках в том же формате записаны числа b и y, а также c и z. В четвертой строке расположено натуральное число n. Гарантируется простота чисел a, b и c.

Формат выходных данных

Выведите одно натуральное число — ответ на задачу.

Ограничения

2 ≤ a, b, c ≤ 97

0 ≤ x ≤ a − 1

0 ≤ y ≤ b − 1

0 ≤ z ≤ c − 1

1 ≤ n ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n = 1, получат не менее 20 баллов.

Решения, верно работающие при x = y = z = 0, получат не менее 20 баллов.

Пояснение к примеру

В примере нужно найти второе по счету число, которое имеет остаток остаток 1 при делении на два (то есть оно нечетное), имеет остаток 2 при делении на три и нацело делится на пять. Первое из таких натуральных чисел — 5, второе — 35.

Примеры тестов

2 1
3 2
5 0
2

35