Проста рекурентність#6090
Вам дано чотири натуральних числа , , і , які визначають таку рекурентну послідовність:
За заданим обчисліть x_n \bmod 1000000007.
Єдиний рядок містить п'ять цілих чисел , , , та (1 \leq a < b \leq 2000, 1 \leq c, d \leq 100, 1 \leq n \leq 10^9).
Виведіть x_n \bmod 1000000007.
Приклад 1