Заданы числа $a, b, c$. Реализуйте рекурсивную функцию: $$ f(n) = \begin{cases} 0, n < 0 \\ a, n = 0 \\ f(n - 1) + b \cdot f(n - 2) + c, n > 0 \end{cases} $$ \InputFile Четыре неотрицательных целых числа $a, b, c~(a, b, c \le 1000), n~(0 \le n \le 1000)$. \OutputFile Выведите значение $f(n)$ по модулю $10^9 + 7$.