Today MLGSwagqu1ckscope5337 said to XXX_5NIPERXXXSCOPEZ69_XXx: "1v1 irl fgt nub il rek u". In order to prepare for the upcoming battle, XXX_5NIPERXXXSCOPEZ69_XXx needs to level up his skill, and, as you know, the best way to do this is to use mtn dew while listening to dubstep at 4:20 Moscow time. The resulting skill is calculated by the formula: f(n) = f(n - 1) + f(n - 2) + f(n / 2), where n is the number of mtn dew liters expressed as an integer. Also, it is known that f(1) = 1 micro$oft point and f(x) = 0 micro$oft point, for x < 1. Help XXX_5NIPERXXXSCOPEZ69_XXx count the received amount of micro$oft poinZ.
Input:
The input is the number n (0 <= n <= 70).
Output:
Output one number - the resulting skill.
Input example:
1
Sample output:
1
Author: Bukov Anton