Задачі
"Проста рекуррентність"
"Проста рекуррентність"
Задано чотири натуральних числа a, b, c та d, які визначають наступну рекурентність:
x_{n }= 1 для n ≤ 0,
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