program bly(input,ouput);
var
  a:array[0..1000,0..1000] of integer;
  n,ans:integer;
  i,j:integer;
  f1,f2:text;
begin
  assign(f1,'chashu.in');
  reset(f1);
  readln(f1,n);
  close(f1);

  a[1,0]:=8;
  ans:=0;
  for i:=1 to n do a[i,i]:=1;
  for i:=2 to n do a[i,0]:=(a[i-1,0]*9) mod 12345;
  for i:=2 to n do begin
    for j:=1 to i-1 do begin
      a[i,j]:=(a[i-1,j-1]+a[i-1,j]*9)mod 12345;
    end;
  end;
  for i:=0 to n do if i mod 2=0 then ans:=(ans+a[n,i]) mod 12345;
  assign(f2,'chashu.out');
  rewrite(f2);
  writeln(f2,ans mod 12345);
  close(f2);
end.