program chashu;
var x1,x2:longint;
ci,co:text;
n:longint;
ls:longint;
jg:longint;
p:boolean;
sz:array[1..1000] of boolean;
procedure change;
begin
if p=false then p:=true
else
p:=false;
end;
procedure go(a:longint);
var x:longint;
begin
if (a>1) and (a<n) then
for x:=0 to 9 do
begin
if x=3 then change;
go(a+1);
if x=3 then change;
end;
if a=1 then
for x:=1 to 9 do
begin
if x=3 then change;
go(a+1);
if x=3 then change;
end;
if a=n then
begin
for x:=0 to 9 do
begin
if x=3 then change;
if p=false then ls:=ls+1;
if x=3 then change;
end;
if ls>12345 then ls:=ls mod 12345;
end;
end;
begin
assign(ci,'chashu.in');
reset(ci);
readln(ci,n);
close(ci);
p:=false;
for x1:=1 to n do sz[x1]:=false;
go(1);
assign(co,'chashu.out');
rewrite(co);
writeln(co,ls);
close(co);
end.