You are at the International Monkey Bars Climbing Competition 2017! Each contestant must climb various stretches of monkey bars during each round. The rules are that you may not more move than 3 bars at a time. Find the number of distinct ways to climb a given section.

**Example**

For n = 4, the output should be

monkeyBars(n) = 7.

There are 7 distinct ways to climb the bars - 3 + 1, 1 + 3, 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, 1 + 1 + 1 + 1, 2 + 2.

**Input/Output**

**[time limit] 4000ms (py3)**

**[input] integer n**Number of bars.

*Guaranteed constraints:*

1 ≤ n ≤ 60.**[output] integer64**Number of distinct ways to climb.

## Solution

When investigating the series, we can see that the emerging pattern is known as the tribonacci number sequence - a generalization of fibonacci numbers. The definition is

\[T_n = T_{n-1} + T_{n-2} + T_{n-3}\]

for \(n\geq 4\) and \(T_1=T_2=1, T_3=2\). This recurrence relation can be implemented with Python like this:

```
def monkeyBars(n):
a = b = 1
c = 2
while n:
a, b, c = b, c, a + b + c
n-= 1
return a
```