Recursion - 3#11250
Sign in

Recursion - 3

1 second
128 megabytes
Very easy

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}

Input

Four nonnegative integers: a, b, c~(a, b, c \le 1000) and n~(0 \le n \le 1000).

Output

Print the value of modulo 10^9 + 7.

Examples

Example 1

Loading
Loading