Задача B. Mirror for numbers

Автор:Anton Karabanov   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

В уездном городе N живут натуральные числа. Сегодня у них праздник, поэтому в парке аттракционов установили новое развлечение — числовое зеркало. Работает оно так: запись числа переводится в двоичную систему счисления, в зеркале его цифры отражаются в обратном порядке (если двоичная запись числа оканчивалась на один или несколько нулей, они отбрасываются). Получившаяся двоичная запись переводится обратно в натуральное число. Например, если к зеркалу подойдет число 26, то его двоичная запись 2610 = 110102 запишется в обратном порядке 10112 (получившийся ведущий ноль отбросится) и в зеркале все увидят число 11.

К зеркалу последовательно подошли все числа, чья запись в двоичной системе счисления состоит ровно из d цифр. Определите, сколько из них увидели свое отражение в зеркале ...

  1. меньше, чем исходное число;
  2. равным исходному числу;
  3. больше, чем исходное число.

Формат входных данных

Входные данные содержат натуральное число d.

Формат выходных данных

Выведите в трех строках три целых числа — ответ на задачу.

Ограничения

1 ≤ d ≤ 50

Пояснение к примеру

В примере дано d = 4. К зеркалу подходили числа, чья длина в двоичной системе счисления равна 4, то есть числа из диапазона от 8 до 15.

Число 8 отразилось как 1, 9 как 9, 10 как 5, 11 как 13, 12 как 3, 13 как 11, 14 как 7 и 15 как 15.

Итого пять чисел отразились меньшими, чем исходные (8, 10, 12, 13 и 14), два — не изменились (9 и 15), одно отразились большим, чем исходное (11).

Примеры тестов

Стандартный вход Стандартный выход
1
4
5
2
1

0.098s 0.024s 15