program chashu;
  const
    max=1000;
    jie=12345;
  var
    a:array[1..max,-1..max]of integer;
    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.