记录编号	2250	评测结果	AAAAAAAAAA
题目名称	查数	最终得分	100
用户昵称	elysian	是否通过	通过
代码语言	Pascal	运行时间	0.022 s
提交时间	2008-09-17 19:27:00	内存使用	0.12 MiB

program yuffie;
const
fin='chashu.in';fout='chashu.out';
var
f1,f2:text;
n:longint;
f:array[1..1001,0..1] of longint;

procedure dp;
var
i:longint;
begin
readln(f1,n);
close(f1);
f[1,0]:=9;
f[1,1]:=1;

for i:=2 to n do
if i<n then
  begin
  f[i,0]:=(f[i-1,0]*9+f[i-1,1])mod 12345;
  f[i,1]:=(f[i-1,0]+f[i-1,1]*9)mod 12345;
  end
else begin
  f[i,0]:=(f[i-1,0]*8+f[i-1,1])mod 12345;
  f[i,1]:=(f[i-1,0]+f[i-1,1]*8)mod 12345;
end;
end;

BEGIN
assign(f1,fin);reset(f1);
dp;
assign(f2,fout);rewrite(f2);
writeln(f2,f[n,0]);

close(f2);
END.