Problem description

Jasio jest wielkim entuzjastą matematyki. Jak każdy szanujący się matematyk, ma on swoją ulubioną liczbę całkowitą dodatnią N. W wolnych chwilach często zapisuje ją na kartce pod różnymi postaciami aby podziwiać jej majestat. Najwspanialszą postacją liczby jest oczywiście jej zapis w systemie binarnym. Ulubioną czynnością Jasia jest zmienianie kolejności cyfr w zapisie binarnym liczby N, rodząc w ten sposób nowe, nigdy wcześniej niezbadane liczby.

Ponad wszystko Jasio ceni sobie piękno kwadratów liczb całkowitych. Ilekroć otrzymana w procesie przestawiania bitów liczba okazuje się być kwadratem, Jasia ogarnia nieziemska rozkosz. Chciałby on ustalić, ile spośród możliwych do uzyskania liczb należy do cudownej rodziny kwadratów. Kunszt matematyczny Jasia oczywiście nie pozwala mu podczas przestawiania bitów na stworzenie liczby z zerami wiodącymi. Przykładowo, dla N = 69 = 1000101₂ może on uzyskać 1010001₂ = 9² oraz 1100100₂ = 10², ale nie 0110001₂ = 7².

Napisz program, który wczyta liczbę N i wypisze, ile różnych kwadratów liczb całkowitych można otrzymać poprzez zamianę kolejności cyfr w jej zapisie binarnym.

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się liczba całkowita N.

Wyjście

Twój program powinien wypisać jeden wiersz zawierający jedną liczbę całkowitą – ile różnych kwadratów liczb całkowitych można otrzymać poprzez zamianę kolejności cyfr w zapisie binarnym liczby N.

Ograniczenia

1 ≤ N ≤ 10¹⁸.

Przykład

9

1

69

2

1337

2