Slinky< /strong> — a spring toy created in 1943 in the USA by Richard James In our country it was simply called Rainbow. All the children loved to launch her down the stairs, counting who would take her down.
Usually "Rainbow" in the hands of the children, it went down to the next step, to the step after one or after 2. (For example, if Rainbow was launched from the 10th step, then it could stop on the 9th, 8th or 7th.)< br />
Let's say there are N steps on the stairs. Determine the number of possible "routes" Rainbows from the top of the stairs to the ground.
Input
A single number is entered \(0 < N < 31\).
Output
Print a single number — number of "routes" Rainbows.
Examples