记录编号	4412	评测结果	AAAAAAAAAA
题目名称	查数	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	0.351 s
提交时间	2008-10-19 12:22:17	内存使用	7.76 MiB

program cch(input,output);
var
 f:array[0..1000,0..1000] of int64;
 n,i,j:integer;
 ans:int64;
begin
 assign(input,'chashu.in');
 assign(output,'chashu.out');
 reset(input);
 rewrite(output);
 readln(n);
 f[1,0]:=8;
 for i:=2 to n do f[i,0]:=f[i-1,0]*9 mod 12345;
 for i:=1 to n do f[i,i]:=1;
 for i:=2 to n do
  for j:=1 to i-1 do
   f[i,j]:=(f[i-1,j-1]+f[i-1,j]*9) mod 12345;
 ans:=0;
 for i:=0 to n do
  if i mod 2=0 then
   inc(ans,f[n,i]);
 write(ans mod 12345);
 close(input);
 close(output);
end.