O fabrică de jucării a primit o comandă pentru construirea
unor cuburi colorate. Cuburile vor fi turnate din material plastic,
după care pe cele şase feţe vor fi lipite autocolante de culori diferite,
avand dimensiunea egala cu dimensiunea feţei. Autocolantele colorate
vin pe bandă rulantă, sunt preluate mecanic şi se lipesc pe fiecare
faţă a cubului. Culorile pe banda rulantă sosesc într-o ordine aleatoare.
Două cuburi se consideră distinct colorate, dacă oricum am roti cubul
al doilea, nu putem să obţinem o coloratură identică cu primul cub.
De exemplu, dacă culorile autocolantelor de pe banda rulantă sunt: (transparent,
zigzag, transparent, transparent, gri, transparent), atunci prin colorarea
feţelor se pot obţine doar două cuburi colorate diferit:
Observaţi, că în cazul 3. dacă cubul se roteşte
în jurul axei verticale cu 90 de grade la stânga, se obţine soluţia 1.
Cerinţă
Cunoscând numărul p
al culorilor disponibile, să se calculeze numărul colorărilor distincte
posibile modulo 666013.
Date de intrare
Fişierul cub.inconţine pe prima linie numărul p
de culori.
Date de ieşire
Fişierul cub.outva conţine o singura linie, pe care va fi scris un singur număr
natural, reprezentând numărul modalităţilor distincte modulo
666013.
Restricţii
1<=p<=7000
Exemple
cub.in
cub.out
Explicaţii
2
10
De exemplu, dacă cele două culori
sunt alb şi gri, avem cazurile:
1 caz: alb, alb, alb, alb, alb, alb,
1 caz: gri, gri, gri, gri, gri, gri,
1 caz: gri, gri, gri, gri, gri, alb,
1 caz: gri, alb, alb, alb, alb, alb,
2 cazuri: gri, gri, alb, alb, alb, alb,
2 cazuri: alb, alb, gri, gri, gri, gri,
2 cazuri: alb, alb, alb, gri, gri, gri.
