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.in conţine pe prima linie numărul p de culori.

Date de ieşire

Fişierul cub.out  va 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. Total: 10 cazuri.
cub.in	cub.out	Explicaţii
6	2226

prof. Szabo Zoltan

Grupul Şcolar "Petru Maior" Reghin

szabozoliposta@yahoo.com