В избыточной двоичной системе счисления, в отличие от обычной двоичной, используется не две цифры, а три —  0, 1 и 2. Заметим, что в данной системе представление чисел может быть неоднозначным. Например, десятичное число 9 можно записать тремя разными способами — 121, 201 и 1001.

Дано целое положительное число N. Определите количество различных способов записать его в избыточной двоичной системе счисления.

Входные данные — одно целое число N (1 ≤ N ≤ 10¹⁸).

Выведите одно целое число — ответ.

Примеры

Входные данные	Выходные данные
9	3