Stefan Dascalescu (stefdasca.ro) (stefdasca) Cerința
Numărul 6 este numărul perfect, deoarece este singurul număr care are suma și produsul divizorilor(fără numărul însuși) egale.
După ce au citit acest fragment plin de înțelepciune, combatanții au descoperit imediat o nouă proprietate frumoasă a numerelor, legată de suma și produsul cifrelor lor. De exemplu, 22 are suma cifrelor egală cu 4, la fel ca și produsul lor. Prin urmare, ei vor acum să aflați dacă descoperirea lor a fost o coincidență sau nu.
Mai exact, ei vă dau un număr natural n și ei vor să aflați câte numere de n cifre există care au suma și produsul cifrelor egale.
Fiindcă numărul poate fi foarte mare, se cere afișarea răspunsului modulo 10^9 + 7.
Date de intrare
Programul citește de la tastatură numărul n,.
Date de ieșire
Programul va afișa pe ecran numărul S, reprezentând numărul căutat.
Restricții și precizări
1 ≤ n ≤ 100000- Pentru teste în valoare de
10de puncte,1 ≤ n ≤ 6 - Pentru teste în valoare de
30de puncte,1 ≤ n ≤ 1000
Exemplu:
Intrare
2
Ieșire
1
Explicație
22 este singurul număr de două cifre care respectă proprietatea dată.