//Problem : Chashu;
//Author  : CaiXinXiao;
//Way     : DT;

Program Chashu;
Const
  MaxN  = 1000;
  Inf   = 'chashu.in';
  Ouf   = 'chashu.out';
Var
  Value : Array[1..2,1..MaxN] of Longint;
  N     : Longint;

Procedure Init;
  Begin
      assign(input,Inf); reset(input);
      assign(output,Ouf); rewrite(output);
      FillChar(Value,sizeof(Value),0);
      Readln(n);
  End;

Procedure Main;
  Var
    r:Longint;
  Begin
    Value[1][1]:=8;
    Value[2][1]:=1;
    For r:=2 to n do
      Begin
        Value[1,r]:=(Value[2,r-1]+Value[1,r-1]*9) Mod 12345;
        Value[2,r]:=(Value[1,r-1]+Value[2,r-1]*9) Mod 12345;
      End;
  End;


Procedure Print;
  Begin
    writeln(Value[1][n]);
    close(input);
    close(output);
  End;

BEGIN
  Init;
  Main;
  Print;
END.