eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

"Проста рекуррентність"

"Проста рекуррентність"

Ліміт часу 8 секунд
Ліміт використання пам'яті 64 MiB

Задано чотири натуральних числа a, b, c та d, які визначають наступну рекурентність:

x_{n }= 1 для n0,

x_{n }= cx_n_{-a }+ dx_n_{-b} для n > 0.

Для заданого n обчисліть x_n mod 1000000007.

Вхідні дані

Єдиний рядок, який містить п'ять цілих чисел a, b, c, d та n (1 a < b 2000, 1 c, d 100, 1 n 10^9).

Вихідні дані

Вывести x_n mod 1000000007.

Приклад

Вхідні дані #1
1 2 1 1 5
Вихідні дані #1
13
Автор Олексій Щепін
Джерело ACM-ICPC Ukraine 2013, 2nd Stage Ukraine, September 10-12, 2013