Bunget Mihai (mihaibun) Cerința
Să se afle câte numere naturale cu n cifre au suma oricăror două cifre alăturate pătrat perfect.
Date de intrare
Fișierul de intrare pepeuri.in conține pe prima linie numărul natural n.
Date de ieșire
Fișierul de ieșire pepeuri.out va conține pe prima linie numărul m, reprezentând numărul numerelor naturale cu n cifre pentru care suma oricăror două cifre alăturate este pătrat perfect. Deoarece acest număr poate fi foarte mare se va afişa rezultatul modulo 10111121.
Restricții și precizări
2 ≤ n ≤ 1.000.000.000
Exemplu:
pepeuri.in
2
pepeuri.out
17
Explicație
Numerele formate cu două cifre, având proprietatea cerută, sunt: 10 , 13 , 18 , 22 , 27 , 31 , 36 , 40 , 45 , 54 , 63 , 72 , 79 , 81 , 88 , 90 , 97, în total 17 numere.