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

Заданы четыре натуральных числа 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.

Примеры