Чтобы подготовиться к предстоящей битве Bonkisilver должен прокачать свой скил, а, как известно, лучшим способом это сделать, является употребление mtn dew при прослушивании дабстепа в 4:20 по МСК. Полученный скилл вычисляется по формуле:
f(n) = f(n - 1) + f(n - 2) + f(n / 2),
где n - количество литров mtn dew, выражаемое целым числом. Операция n/2 означает целочисленное деление числа n на 2.
Также, известно, что
f(1) = 1 microCoinZ
f(x) = 0 microCoinZ, при x < 1.
Помогите Bonkisilver сосчитать полученное количество microCoinZ.
Входные данные
На вход подается число n (0 <= n <= 70).
Выходные данные
Выведите одно число - полученный скилл.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1 |
1 |
PS: Mountain Dew, также MTN DEW — безалкогольный сильногазированный прохладительный напиток, торговая марка американской компании PepsiCo.