记录编号	2495	评测结果	AAAAAAAAAA
题目名称	铺砖	最终得分	100
用户昵称	elysian	是否通过	通过
代码语言	Pascal	运行时间	0.002 s
提交时间	2008-09-22 19:12:32	内存使用	38.26 MiB

program elysian;
const
fin='puzhuan.in';fout='puzhuan.out';
var
n:longint;
f:array[0..10000000] of longint;
f1,f2:text;

procedure init;
var
i:longint;
begin
assign(f1,fin);reset(f1);
readln(f1,n);
close(f1);
for i:=0 to n do
f[i]:=1;
end;

procedure dp;
var
i,j:longint;
begin
for i:=1 to n do
f[i]:=(f[i-1]+f[i-2]*2) mod 12345;
end;

begin
init;
dp;
assign(f2,fout);rewrite(f2);
writeln(f2,f[n]);
close(f2);

end.