Se dă un numar natural N.

Cerinţă

Se cere să se afle numărul total de moduri în care 2^N se poate scrie ca produs de cifre strict mai mari decât 1.

Date de intrare

Fişierul de intrare 2ndesc.in va conţine o singură linie pe care este scris numărul natural N.

Date de ieşire

Fişierul de ieşire 2ndesc.out va conţine o singură linie pe care se va scrie un număr natural, reprezentând soluţia problemei. Deoarece numărul poate fi foarte mare, se cere să se afişeze modulo 666013.

Restricţii

• 1 <= N <= 1000000000 (10⁹)
• Se acceptă şi produsul de o singură cifră (pentru N=2, se acceptă şi soluţia 4).

Exemplu

2ndesc.in	2ndesc.out	Explicaţie	2ndesc.in	2ndesc.out
4	7	Pentru N=4 avem următoarele soluţii: 2*2*2*2 2*2*4 2*4*2 4*2*2 2*8 8*2 4*4	1238	623122

Andrei Diaconeasa

Facultatea de Matematica si Informatica, Universitatea Bucuresti

andrei.diaconeasa@gmail.com