记录编号	4999	评测结果	AAAAAAAAAA
题目名称	查数	最终得分	100
用户昵称	zpl123	是否通过	通过
代码语言	Pascal	运行时间	0.169 s
提交时间	2008-10-24 14:03:31	内存使用	3.93 MiB

program chashu;
var
n:integer;
x:array[1..1000,-1..1000]of longint;
max:longint;

procedure ini;
begin
assign(input,'chashu.in');
reset(input);
assign(output,'chashu.out');
rewrite(output);
readln(n);
close(input);
fillchar(x,sizeof(x),0);
max:=0;
end;

procedure main;
var
i,j:integer;
begin
x[1,0]:=8;
x[1,1]:=1;

for i:=2 to n do
 for j:=0 to i do
  x[i,j]:=(x[i-1,j-1]+x[i-1,j]*9)mod 12345;
for i:=0 to n do
 if (i mod 2=0) then max:=max+x[n,i];
end;

begin
ini;
main;
writeln(max mod 12345);
close(output);
end.