Program Puzhuan;
Const
  MaxN  = 1000;
  Inf   = 'puzhuan.in';
  Ouf   = 'puzhuan.out';
Var
  Value : Array[0..MaxN] of Longint;
  N     : Longint;
Procedure Init;
  Begin
    assign(input,Inf); reset(input);
    assign(output,Ouf); rewrite(output);
    Readln(n);
  End;

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

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

BEGIN
  Init;
  Main;
  Print;
END.