Cerința

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.

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 conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

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

Restricții și precizări

• pentru 20% din teste 1 ≤ N ≤ 6
• pentru alte 20% din teste N ≤ 12
• pentru alte 30% din teste N ≤ 10.000
• pentru alte 30% din teste N ≤ 1.000.000

Exemplu:

nrecou.in

3

nrecou.out

9

Explicație

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