Semnal

Un semnal digital reprezintă o succesiune de date reprezentate cu ajutorul a două niveluri de tensiune electrică denumite $0$ logic și $1$ logic și sunt prezente în toate electronicele digitale, în special în echipamentele de calcul și în cele utilizate în transmisia de date.
Reprezentarea grafică sau așa numita formă de undă a unui semnal digital este o succesiune neîntreruptă de linii orizontale de nivel $0$ sau de nivel $1$, unite prin linii verticale, conform imaginii alăturate.

Cerință

Fie $L$ un număr natural nenul. Se consideră un fir neîntrerupt de lungime $L$.

Să se determine numărul de forme de undă diferite notat cu $U$ care se pot realiza folosind acest fir respectând următoarele proprietăți:

• O formă de undă începe și se termină pe nivelul logic $0$;
• O formă de undă folosește cel mult două niveluri logice;
• Lungimile liniilor orizontale și verticale sunt doar numere naturale nenule;

Două forme de undă se consideră diferite dacă diferă prin cel puțin o linie.

Exemplu: Pentru $L = 5$ se pot realiza $U = 8$ forme de undă diferite, conform figurii următoare:

Date de intrare

Pe prima linie se va găsi numărul natural $L$.

Date de ieșire

Pe prima linie se va găsi restul împărțirii numărului natural $U$ la $3 \ 000 \ 017$.

Restricții și precizări

• $1 \leq L \leq 10^6$;
• Pentru $16$ puncte, $1 \leq L \leq 34$;
• Pentru $20$ de puncte, $35 \le L \leq 20 \ 000$;
• Pentru $64$ de puncte, $20 \ 001 \leq L \leq 10^6$;

Exemplul 1

stdin

5

stdout

8

Explicație

Se pot forma $U = 8$ forme de undă diferite folosind un fir de lungime $L = 5$ respectând proprietățile cerute, conform exemplului de mai sus.

Exemplul 2

stdin

2022

stdout

177722

Explicație

Restul împărțirii numărului $U$ ce reprezintă numărul de forme de undă diferite ce se pot forma folosind un fir de lungime $L = 2022$ la $3000017$ este $177722$.

Exemplul 3

stdin

470926

stdout

19116

Explicație

Restul împărțirii numărului $U$ ce reprezintă numărul de forme de undă diferite ce se pot forma folosind un fir de lungime $L = 470926$ la $3000017$ este $19116$.