记录编号	2735	评测结果	AAAAAAAAAA
题目名称	行进方案	最终得分	100
用户昵称	elysian	是否通过	通过
代码语言	Pascal	运行时间	0.021 s
提交时间	2008-09-25 19:48:29	内存使用	0.11 MiB

program elysian;
const
fin='zbfa.in';fout='zbfa.out';
var
n:longint;
f:array[0..1000] of longint;
f1:text;

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

procedure init;
begin
assign(f1,fin);reset(f1);
readln(f1,n);
close(f1);
end;

begin
init;
assign(f1,fout);rewrite(f1);
f[0]:=1;
f[1]:=3;
dp;
writeln(f1,f[n]);
close(f1);
end.