program puiss_mat_mod;

const LONG=3;
type mat_int = array [1..LONG,1..LONG] of integer;

procedure saisie(var A : mat_int);
var i,j : integer;
begin
   writeln('Saisie d une matrice carree de taille ',LONG,' :');
   for i:=1 to LONG do
   begin
      writeln('entree de la ligne numero ',i,' :');
      for j:=1 to LONG do readln(A[i,j]);
   end;
end;

procedure visu(A : mat_int);
var i,j : integer;
begin
   for i:=1 to LONG do
   begin
      write('[ ');
      for j:=1 to LONG-1 do write(A[i,j],' , ');
      writeln(A[i,LONG],' ]')
   end;
end;

procedure mult(A : mat_int;B:mat_int;p:integer;var C:mat_int);
var i,j,k,tmp : integer;
begin
   for i:=1 to LONG do
      for j:=1 to LONG do
	 begin
	    tmp:=0;
	    for k:=1 to LONG do
	       tmp:=tmp+(A[i,k]*B[k,j] mod p);
	    C[i,j]:=tmp mod p;
	 end;
end;

procedure mat_id(var Id: mat_int);
var i,j	: integer;
begin
   for i:=1 to LONG do
      for j:=1 to LONG do
	 if (j=i) then Id[i,j]:=1 else Id[i,j]:=0;
end;

procedure puiss_naive(A	: mat_int;n,p:integer;var R:mat_int);
var k	: integer;
begin
   if n=0 then mat_id(R)
   else
   begin
      R:=A;
      for k:=2 to n do mult(A,R,p,R);
   end;
end;

function pair(n	: integer):boolean;
begin
   if (n mod 2=0) then pair:=true else pair:=false
end;

procedure puiss_dicho(	  A : mat_int;n,p:integer;var R:mat_int);
var k	     : integer;
   puiss,res : mat_int;
begin
   if n=0 then mat_id(R)
   else if n=1 then R:=A
   else
   begin
      mat_id(res);
      puiss:=A;
      k:=n;
      while (k>1) do
      begin
	 if not pair(k) then mult(res,puiss,p,res);
	 mult(puiss,puiss,p,puiss);
	 k:=k div 2;
      end;
      mult(res,puiss,p,R); 
   end;
end;



var A,B,C,I:mat_int;

BEGIN
   {clrscr;}
   writeln('saisie de A');
   saisie(A);
   visu(A);
   readln;

   writeln('puissance naive');
   puiss_naive(A,151500,7,C);
   visu(C);
   readln;
   writeln('puissance dicho');
   puiss_dicho(A,151500,7,C);
   visu(C);
   readln;
END.