program EmberAsh;
const
dx:array[1..3]of integer=(-1,0,1);
dy:array[1..3]of integer=(0,1,0);
var
a:Array[-1000..1000,0..2000]of boolean;
x,y:array[1..1000]of longint;
num:array[1..1000]of longint;{record}
f:array[0..10000]of int64;
ss,head,i,j,k,n,h:longint;
x1,x2,x3,y1,y2,y3:longint;

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