Fişierul intrare/ieşire:nrecou.in, nrecou.outSursăad-hoc
AutorAdăugată destocarulCosmin-Mihai Tutunaru stocarul
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

NREcou

Dorind să inventeze ceva nou Mate a inventat numerele "ecou". Un număr natural A se numeşte număr-ecou dacă există un număr natural B cu proprietatea că numărul A se poate obţine prin concatenarea de un număr de ori (cel puţin de două ori) a numărului B. De exemplu numărul 313313 este număr-ecou, iar 31313 nu este număr-ecou.

Cerinţă

Mate şi-a propus să afle câte numere-ecou sunt printre numerele naturale care au exact N cifre. Deoarece acest număr poate fi foarte mare, se va afişa doar restul împărţirii rezultatului la 10^9+17.

Date de intrare

Fişierul de intrare nrecou.in contine, pe primul rând, numărul N.

Date de ieşire

În fişierul de ieşire nrecou.out se va afişa, pe primul rând, valoarea cerută.

Restricţii

  • pentru 20% din teste 1≤N≤6
  • pentru alte 20% din teste N≤12
  • pentru alte 30% din teste N≤10^4
  • pentru alte 30% din teste N≤10^6

Exemplu

nrecou.innrecou.out
3
9

Explicaţie

Numerele ecou cu trei cifre sunt 111, 222, 333, 444, 555, 666, 777, 888, 999.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?