Program Zbfa;
Const
  MaxN  = 1000;
  Inf   = 'zafa.in';
  Ouf   = 'zafa.out';
Var
  Value : Array[0..MaxN] of Longint;
  i,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;
  Begin
    Value[1]:=3; Value[2]:=7;
    For i:=3 to n do Value[i]:=(2*Value[i-1]+Value[i-2])mod 12345;
  End;

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

BEGIN
  Init;
  Main;
  Print;
END.