NREcou

nrecou

== include(page="template/taskheader" task_id="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.
 
h2. 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$.

Poveste şi cerinţă...

h2. Date de intrare

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

Fişierul de intrare $nrecou.in$ ...

h2. Date de ieşire

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

În fişierul de ieşire $nrecou.out$ ...

h2. 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$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. nrecou.in |_. nrecou.out |

| 3
| 9

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

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

...

== include(page="template/taskfooter" task_id="nrecou") ==