bsir

Se dă un număr natural $N$.
Definim un bşir de lungime N ca fiind şirul $x_0, x_1, \dots, x_{N-1}$, unde

• $x_i = 1$ dacă $i$ are un număr impar de biţi egali cu $1$ în reprezentare binară
• $x_i = 0$ dacă $i$ are un număr par de biţi egali cu $1$ în reprezentare binară

De exemplu, pentru $N = 7$ obţinem următorul bşir de lungime $7$: $0110100$

Explicaţii privind obţinerea bşir-ului:

Cerinţă

Determinaţi numărul $M$ de secvenţe palindromice de lungime cel puţin $2$ dintr-un bşir de lungime $N$.

Date de intrare

Fişierul de intrare bsir.in conţine pe prima linie numărul natural $N$.

Date de ieșire

Fişierul de ieşire bsir.out va conţine $M$ modulo $30 \ 103$ (restul împărţirii lui $M$ la $30 \ 103$).

Restricții și precizări

• $2 \leq N \leq 10^{18}$
• Secvenţa $x_i, x_{i+1}, \dots, x_{j-1}, x_j$ se numeşte palindromică dacă $x_i = x_j, x_{i+1} = x_{j-1}, \dots$

Exemplul 1

bsir.in

10

bsir.out

8

Exemplul 2

bsir.in

21

bsir.out

30