Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
Рассмотрим линейную функцию 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.