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.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("nrecou.in");
ofstream cout("nrecou.out");

int n , D[10000000] ; 
long long nr , rez;

int main()
{
    cin >> n;
    for(int d = 2 ; d <= n && n / d >= 2 ; d++)
        if(n % d == 0)
        {
            nr = 9;
            int x = d;
            for(int j = 1 ; j < x ; j++)
                nr = (nr * 10) % 1000000017;
            for(int p = 2 ; p <= x / 2 ; p++)
            {
                if(x % p == 0) nr -= D[p];
                if(nr < 0) nr += 1000000017;
            }
            nr -= 9;
            if(nr < 0) nr += 1000000017;
            D[d] = nr % 1000000017;
            rez = (nr + rez) % 1000000017;
        }
    cout<<(rez+9)%1000000017;
    return 0;
}