Dynamic programming is the “art” of constructing a certain state based on the previous states. When doing computations, we often rely on the previous values calculated during the execution. Fibonacci numbers are a great example that can be calculated using dynamic programming:

So, to calculate fib(2) we would use the values fib(1) and fib(0). Therefore, obtaining the value for fib(2) = 1. To get the next value in the Fibonacci sequence, we should make use of the value we calculated previously - fib(3) = fib(2) + fib(1) = 1 + 1 = 2. Similarly, fib(4) = fib(3) + fib(2) = 2 + 1 = 3 and fib(5) = fib(4) + fib(3) = 3 + 2 = 5, and the sequence goes on.

On each iteration, we calculate the current value of the Fibonacci sequence using the previous states that we calculated beforehand. This can be implemented with a list:

n = ...
fib = [0, 1] # fib[0] = 0, fib[1] = 1
for i in range(2, n + 1):
fib.append(fib[i - 1] + fib[i - 2])
print(fib[n])

For a value n = 5, the program would print 5, while for a value n = 7 it would print 13.

The process of repeatedly calculating the current state (the current Fibonacci number in our case) using the previous states is the essence of Dynamic Programming.

💡

Dynamic programming is a technique to construct the current state based on the previous states.

Challenge - Tribonacci numbers

After playing with Fibonacci numbers, you got bored and decided to play with Tribonacci numbers instead. Tribonacci numbers are defined as:

Your task is to find the n-th Tribonacci number.

Input

The input contains a single integer n (1 ≤ n ≤ 30).

Output

The output should contain the n-th Tribonacci number.