Since ~f(1)~, ~f(2)~, and ~f(3)~ are provided in the input, and a formula for each following term is provided, we can use a loop to calculate all the values ~f(4), f(5), \ldots f(n)~. Make sure to store at least the ~3~ most recent answers in an array to be used in the formula and mod each answer by ~10^9+7~.

Afterwards, output the value for ~f(n)~.

Time complexity: ~\mathcal{O}(n)~.

Sample solution written in Python

Please try implementing the solution yourself rather than copy-pasting the official solution.

a, b, c, n = map(int, input().split())
f = [None] * (n + 1) # Initialize empty array
f[1] = a; f[2] = b; f[3] = c
for i in range(4, n + 1): # calculate f(4) ... f(n)
    f[i] = (f[i - 1] + f[i - 2] - f[i - 3]) % (1000000007) # use the given formula and mod
print(f[n])