Cerința

Gioni este un elev foarte pasionat de informatică și îndrăgește în special problemele care se rezolvă cu tehnica programării dinamice. El are un număr natural n și vrea să știe pentru fiecare numar i de la 1 la n câte numere cu i cifre nu sunt palindromuri. Fiindcă acest număr poate să fie foarte mare, se cere afișarea lui modulo 666013.

Date de intrare

Fișierul de intrare no_pals.in conține pe prima linie numărul n.

Date de ieșire

Fișierul de ieșire no_pals.out va conține pe fiecare linie i, de la 1 la n, numărul de numere de i cifre care nu sunt palindromuri.

Restricții și precizări

• 1 ≤ n ≤ 100000

Exemplu

no_pals.in

3

no_pals.out

0
81
810

Explicație

Toate numerele de o cifra sunt palindromuri. Sunt 90 de numere de 2 cifre, dintre care 9 sunt palindromuri. Sunt 900 de numere de 3 cifre, dintre care 90 sunt palindromuri.

#include <bits/stdc++.h>

using namespace std;

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

#define MOD 666013

int n;
long long nr = 1, nrnr = 9, rez;

int calc(int x)
{
    if (x == 1)return 0;
    if (x % 2 == 0)
    {
        if (x == 2)nr *= 9;
        else nr *= 10;
        nr %= MOD;
        rez = nrnr - nr;
    }
    else
    {
        long long aux = (nr * 10)%MOD;
        rez = nrnr - aux;
    }


    while(rez < 0)rez += MOD;
    rez %= MOD;
    return rez;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        cout << calc(i) << '\n';
        nrnr *= 10;
        nrnr %= MOD;
    }

    return 0;
}