program MayLava;
var
 n:longint;
 a:array[0..1000,0..1000]of integer;
procedure start;
 var
  f:text;
  i:integer;
 begin
  assign(f,'chashu.in');
  reset(f);
  readln(f,n);
  close(f);
  a[1,0]:=8;
  for i:=1 to n do a[i,i]:=1;
 end;
procedure main;
 var
  i,j,sum:longint;
  f:text;
 begin
  for i:=2 to n do
   a[i,0]:=(a[i-1,0]*9) mod 12345;
  for i:=2 to n do
   for j:=1 to i-1 do
    a[i,j]:=(a[i-1,j-1]+a[i-1,j]*9) mod 12345;
  for i:=0 to n do
   if i mod 2=0 then
    sum:=(sum+a[n,i]) mod 12345;
  assign(f,'chashu.out');
  rewrite(f);
  writeln(f,sum mod 12345);
  close(f);
 end;
BEGIN
 start;
 main;
END.