Kevin is going up the stairs. The stairs have n steps,

Kevin can take one, two or three steps at a time,

To achieve a program to calculate the number of ways to complete the stairs.

input

Number of stairs n (n > = 3)

output

How many ways does Kevin have to walk up the stair

Example:

Input:

8

Output:

81