Bunget Mihai (mihaibun) Cerința
Un număr natural se numește SuperPerfect dacă cifrele sale sunt pătrate perfecte și suma oricăror două cifre alăturate este pătrat perfect. Se cere să se afle câte numere SuperPerfecte cu N cifre există.
Date de intrare
Fișierul de intrare superperfecte.in conține pe prima linie numărul N.
Date de ieșire
Fișierul de ieșire superperfecte.out va conține pe prima linie numărul M, reprezentând numărul numerelor SuperPerfecte cu N cifre, modulo 555557.
Restricții și precizări
1 ≤ N ≤ 1.000.000.000
Exemplu:
superperfecte.in
3
superperfecte.out
12
Explicație
Cele 12 numere SuperPerfecte cu 3 cifre sunt : 100 , 101 , 104 , 109 , 400 , 401 , 404 , 409 , 900 , 901 , 904 , 909 .