Определим бесконечную последовательность А следующим образом:

Ai = 1, i ≤ 0,

Ai = Aint(i/p)-x + Aint(i/q)-y, i ≥ 1

По заданным n, p, q, x и y необходимо вычислить n-ый элемент последовательности A (индексы нумеруются с 0).

Входные данные

Пять целых чисел n, p, q, x, y (0 ≤ n ≤ 1013, 2 ≤ p, q ≤ 109, 0 ≤ x, y ≤ 109).

Выходные данные

Вывести значение An.