program day5_1;
 var
     n,i:integer;
     ans:longint;
     f:array[1..1000,1..3] of longint;

 begin
  assign(input,'zbfa.in');
  assign(output,'zbfa.out');
  reset(input); rewrite(output);
  readln(n);
  for i:=1 to 3 do
  f[1,i]:=1;
  for i:=1 to n-1 do
   begin
   f[i+1,1]:=(f[i,1]+f[i,2]+f[i,3]) mod 12345;
   f[i+1,2]:=(f[i,1]+f[i,2]) mod 12345;
   f[i+1,3]:=(f[i,1]+f[i,3]) mod 12345
   end;
  for i:=1 to 3 do
  ans:=(ans+f[n,i]) mod 12345;
  writeln(ans);
  close(input); close(output);
 end.