D. Итерированная линейная функция
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим линейную функцию f(x) = Ax + B. Введём обозначение g(0)(x) = x и g(n)(x) = f(g(n - 1)(x)), при n > 0. Для заданных целых значений A, B, n и x найдите значение g(n)(x) по модулю 109 + 7.

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

В единственной строке находятся четыре целых числа A, B, n и x (1 ≤ A, B, x ≤ 109, 1 ≤ n ≤ 1018) — параметры из условия задачи.

Обратите внимание, что данное значение n может быть слишком большим, поэтому вы должны использовать 64-битный тип данных. В языке C++ вы можете использовать тип long long и в языке Java вы можете использовать тип long.

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

Выведите одно целое число s — значение g(n)(x) по модулю 109 + 7.

Примеры
Входные данные
3 4 1 1
Выходные данные
7
Входные данные
3 4 2 1
Выходные данные
25
Входные данные
3 4 3 1
Выходные данные
79