Счёт робота по странному правилу

В технопарке робот считает «очки энергии» по правилу, которое каждый раз задают заново.

Для целого x функция F(x) определена так:

• если x <= 1, то F(x) = x;
• иначе F(x) = a * F(x-1) + b * F(x div 2) + c.

Тебе дали числа a, b, c и аргумент n. Найди значение F(n) по модулю 10^9+7.

Важно: числа a, b, c приходят во входных данных (это часть задания), они не фиксированы заранее.

Формат ввода: Одна строка: четыре целых числа a, b, c, n.

Формат вывода: Одно целое число — F(n) по модулю 10^9+7.

Ограничения:

• 1 <= n <= 10^6
• 0 <= a, b, c <= 100

Пример Ввод:

1 1 1 5

Вывод:

13