Recursion - 3

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

The numbers $a, b, c$ are given. Implement the recursive function:

f (n) = ⎩ ⎨ ⎧ 0, n < 0 a, n = 0 f (n - 1) + b \cdot f (n - 2) + c, n > 0

Input

Four nonnegative integers $a, b, c (a, b, c \leq 1000), n (0 \leq n \leq 1000)$ .

Print the value of $f (n)$ modulo $1 0^{9} + 7$ .

Input #1

Answer #1

Submissions 1K

Acceptance rate 28%