Problems
Recursion - 3
Recursion - 3
The numbers $a, b, c$ are given. Implement the recursive function:
$$
f(n) = \begin{cases}
0, n < 0 \\
a, n = 0 \\
f(n - 1) + b \cdot f(n - 2) + c, n > 0
\end{cases}
$$
\InputFile
Four nonnegative integers $a, b, c~(a, b, c \le 1000), n~(0 \le n \le 1000)$.
\OutputFile
Print the value of $f(n)$ modulo $10^9 + 7$.
Input example #1
4 2 3 3
Output example #1
35