记录编号	4497	评测结果	AAAAAAAAAA
题目名称	查数	最终得分	100
用户昵称	zhai	是否通过	通过
代码语言	Pascal	运行时间	0.167 s
提交时间	2008-10-20 19:07:52	内存使用	3.93 MiB

program chashu;
  const
    max=1000;
    jie=12345;
  var
    a:array[1..max,-1..max]of longint;
    n:integer;
    ans:longint;
    f1,f2:text;
    procedure ini;
      var
        i:integer;
      begin
        assign(f1,'chashu.in');reset(f1);
        assign(f2,'chashu.out');rewrite(f2);
        read(f1,n);
        fillchar(a,sizeof(a),0);
        a[1,0]:=8;
        for i:=1 to n do inc(a[i,i]);
        close(f1);
        ans:=0;
      end;
    procedure main;
      var
        i,j:integer;
      begin
        for i:=2 to n do
          for j:=0 to i-1 do begin
            a[i,j]:=a[i-1,j]*9+a[i-1,j-1]*1;
            a[i,j]:=a[i,j]mod jie;
          end;
        for i:=0 to n do
          if i mod 2=0 then begin
            inc(ans,a[n,i]);
            ans:=ans mod jie;
          end;
        write(f2,ans);
        close(f2);
      end;
  begin
    ini;
    main;
  end.