记录编号	4408	评测结果	AAAAAAAAAA
题目名称	查数	最终得分	100
用户昵称	王瑞祥K	是否通过	通过
代码语言	Pascal	运行时间	0.143 s
提交时间	2008-10-19 12:15:20	内存使用	3.93 MiB

program chashu(input,output);
var
 a:array[0..1000,0..1000]of longint;
 n,i,j,k:longint;
begin
 assign(input,'chashu.in');assign(output,'chashu.out');
 reset(input);rewrite(output);
 read(n);
 if n=1 then writeln(8)
 else begin
  fillchar(a,sizeof(a),0);
  a[1,0]:=8;
  for i:=2 to n do a[i,0]:=(a[i-1,0]*9)mod 12345;
  for i:=1 to n do a[i,i]:=1;
  for i:=2 to n do
   for j:=1 to i-1 do
    a[i,j]:=(a[i-1,j-1]+a[i-1,j]*9)mod 12345;
  k:=0;
  for i:=0 to n do
   if i mod 2=0 then k:=(k+a[n,i])mod 12345;
  write(k mod 12345);
 end;
 close(input);close(output);
end.