Problem description
Alicja i Bob grają w grę Nim na jeden stosik, a że znudziła im się już podstawowa wersja, to postanowili nieco zmienić zasady. Brzmią one teraz następująco: na stole leży N kamieni, gracze wykonują ruchy na przemian, a ten kto nie może wykonać ruchu przegrywa. Jak zwykle, Alicja zawsze zaczyna. W każdym ruchu wolno zabrać ze stosu pewną niezerową liczbę kamieni, o ile nie przekracza ona połowy liczby wszystkich kamieni obecnie leżących na stole. Wyjątek stanowi sytuacja, gdy na stole pozostał tylko jeden kamień, wtedy gracz wykonujący ruch może go zabrać ze stołu pozostawiając pusty stół dla przeciwnika.
Na przykład: gdy na stole leży 5 kamieni, wolno zabrać 1 lub 2 kamienie, ale 3, 4 i 5 już nie.
Mówimy, że gracz ma strategię wygrywającą, jeśli jest w stanie wygrać niezależnie od ruchów przeciwnika. Alicja chciałaby wiedzieć, dla jakich N posiada strategię wygrywającą. Pomóż jej!
Napisz program, który: wczyta ile kamieni początkowo znajduje się na stole, określi czy Alicja ma strategię wygrywającą i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym i jedynym wierszu wejścia znajduje się jedna nieujemna liczba całkowita N oznaczająca początkową liczbę kamieni na stole.
Wyjście
Twój program powinien wypisać na standardowe wyjście jedno słowo
TAK, gdy Alicja ma strategię wygrywającą lub
NIE w przeciwnym przypadku.
Ograniczenia
0 ≤ N ≤ 1018.
Podzadania
W testach wartych łącznie 40% punktów dodatkowo zachodzi warunek N ≤ 3 000.
Przykład
| Input | Output | |
|
|
| Input | Output | |
|
|
| Input | Output | |
|
|