Your friend likes walking up stairs.
He likes walking up stairs so much that everytime, he attempts to walk up stairs in a way he never did before.
When walking up stairs, he either takes one step up or three steps up at once.
Specifically, given a staircase with N levels, he would decide a sequence of steps (composed of 1s and 3s) to take, such that the sum of the sequence is N.
Two ways of walking up stairs are different if and only if the sequence of steps differ.
For example, given a stairs with 5 floors, he has 4 unique ways of walking up the stairs:
a. [1, 1, 3]
b. [1, 3, 1]
c. [3, 1, 1]
d. [1, 1, 1, 1, 1]
Given N, find out how many times your friend may enjoy walking the stairs up in a unique way.
Smart as your friend is, figured out that f(n), the number of ways to walk up n levels, may be described as the following:
f(n) = f(n - 1) + f(n - 3), if n > 2
f(n) = 1, otherwise
N
(N is a positive integer in between 1 and 116)
A positive integer indicating the number of unique ways to walk up the stairs, with a trailing newline character.