At the top of the ladder, which contains N stairs, there is a ball that starts jumping down them to the base. The ball can jump to the next step, to the step after one or after 2. (That is, if the ball lies on the 8th step, then it can move to the 5th, 6th or 7th.) Determine the number of possible " ;routes" ball from the top to the ground.
Input
Enter a single number 0 < N < 31.
Output
Print a single number — number of routes.
Examples