program chashu;
var
  a:array[1..1001]of longint;
  n:longint;
procedure ini;
Begin
  assign(input,'chashu.in');
  assign(output,'chashu.out');
  reset(input); rewrite(output);
  readln(n);
End;
procedure go;
var
  i,j,k,t:longint;
Begin
  a[1]:=9; t:=a[1];
  for i:=2 to n do begin
    k:=1;
    if (i-1)>5 then k:=99999
      else for j:=1 to (i-1)do k:=k*10;
    a[i]:=((t*8) mod 12345)+((k-t) mod 12345);
    t:=(t+a[i]) mod 12345;
  end;
End;
procedure ouo;
Begin
  writeln(a[n]);
  close(input);
  close(output);
End;
Begin
  ini;
  go;
  ouo;
End.