Farmer John поручил коровам искать разные наборы чисел с заданной суммой. Используются только целые степени 2. Вот все возможные наборы с суммой 7:

1) 1+1+1+1+1+1+1

2) 1+1+1+1+1+2

3) 1+1+1+2+2

4) 1+1+1+4

5) 1+2+2+2

6) 1+2+4

Помогите FJ подсчитать все представления целого $N$ ($1 \le N \le 1{,}000{,}000$).

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

Одна строка с одним целым $N$.

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

Число способов представить $N$ указанной суммой. Оно может быть огромным, поэтому выведите только последние 9 цифр десятичной записи.

Примеры

Входные данные 1

7

Выходные данные 1

6

Задача 1: Представления суммы