Fie secvența S(x) care se construiește astfel:

• S(1)=x
• S(n+1)=S(n) XOR [S(n)/2], unde [x] se definește ca parte întreagă din x, iar XOR este operația clasică „sau exclusiv”.

Cerința

Dându-se un număr natural k, aflați numărul de numere naturale x pentru care S(k+1)=S(1)=x este adevărat. Deoarece numărul poate fi foarte mare, afișați rezultatul modulo 1000000007.

Date de intrare

Fișierul de intrare secventa.in se găsește un singur număr natural k.

Date de ieșire

Fișierul de ieșire secventa.out va conține pe prima linie un singur număr – răspunsul problemei modulo 1000000007.

Dacă pentru un număr k există o infinitate de numere x care respectă cerința, se va afișa numărul -1.

Restricții și precizări

• 1 ≤ k ≤ 1019

Exemplul 1

secventa.in

2

secventa.out

3

Exemplul 2

secventa.in

260

secventa.out

15

Explicație

Pentru primul exemplu, sunt 3 numere ce respectă cerința: 1, 2 și 3. Înlocuirea în formula din cerință confirmă acest lucru.