program ex;
type
 ss=array[1..1000,0..1000]of longint;
var
 f1,f2:text;
 a:ss;
 n,t:longint;
procedure init;
 var
  i:integer;
 begin
  assign(f1,'chashu.in');
  assign(f2,'chashu.out');
  reset(f1);
  rewrite(f2);
  readln(f1,n);
  close(f1);
  a[1,0]:=8;
  for i:=2 to n do
   a[i,0]:=(a[i-1,0]*9)mod 12345;
  for i:=1 to n do
   a[i,i]:=1;
 end;
procedure main;
 var
  i,j:integer;
 begin
  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;
  t:=0;
  for i:=0 to n do
   if (i mod 2=0)then
    t:=(t+a[n,i])mod 12345;
  writeln(f2,t);
 end;
begin
 init;
 main;
 close(f2);
end.