A function ~f(x)~ has been described as follows:

$$\displaystyle f(x) = f(x-1) + f(x-2) - f(x-3)$$ for all ~x \ge 1~, with ~f(1) = a, f(2) = b~, and ~f(3) = c~.

Can you determine ~f(n)~ modulo ~10^9 + 7~?

Constraints

~1 \le n \le 10^6~

~-10^9 \le a, b, c \le 10^9~

Input Specification

The first and only line of input will contain ~a~, ~b~, ~c~, and ~n~ space-separated.

Output Specification

Output an integer in the range ~[0, 10^9+7)~, the value of ~f(n)~ modulo ~10^9 + 7~.

Sample Input 1

5 6 7 8

Sample Output 1

12

Explanation for Sample Output 1

The value of ~f(x)~ for ~x = 1...8~ is:

~5~, ~6~, ~7~, ~8~, ~9~, ~10~, ~11~, ~12~

Sample Input 2

3 1 2 8

Sample Output 2

1000000005