Олимпиадный тренинг

Задача . D. Итерированная линейная функция

Задача

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

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

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	3 4 1 1	7
2	3 4 2 1	25
3	3 4 3 1	79

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет