Muresan Ciprian (mcip1977) Se dă un număr natural nenul n. Se construiește mulțimea numerelor formate din n cifre care au proprietatea că nu conțin cifre alăturate care să fie prime. De exemplu 1476 este un număr corect format, dar 1537 nu este pentru că are cifrele alăturate 5 și 3 sau 3 și 7 cu proprietatea că sunt prime.
Cerința
Să se determine câte numere formate din n cifre au proprietatea că nu au cifre alăturate care să fie prime. Pentru că acest număr poate fi foarte mare, se va determina modulo 666013.
Date de intrare
Programul citește de la tastatură numărul n.
Date de ieșire
Programul va afișa pe ecran numărul modulo 666013 al numerelor formate din n cifre au proprietatea că nu au cifre alăturate care să fie prime.
Restricții și precizări
2 ≤ n ≤ 100.000
Exemplu:
Intrare
2
Ieșire
74