Ліміт часу: 1 секунд Ліміт пам'яті: 3000 K Ліміт виведення: 2 K
Завдання
Над рядочком 01 виконаємо наступні операції: Скопіюємо в кінець рядочка самого себе (отримаємо 0101) В другій половині рядка всі 0 змінимо на 1, а всі 1 на 0 (отримаємо 0110) Над рядочком 0110 виконаємо ті самі операції. Отримаємо 01101001. І т. д.Таким чином отримаємо нескінченний рядочок нулів та одиниць.Ваше завдання – знайти n-тий символ такого рядочка.
Вхідні дані
В єдиному рядку записане єдине число N (1 <= N <= 2000000000).
