program chashu;
var
  i,j,n:integer;
  max,t,t2:int64;
begin
  assign(input,'chashu.in');
  assign(output,'chashu.out');
  reset(input);
  rewrite(output);
  readln(n);
  t2:=100000;
  t2:=t2*100000;
  t2:=t2*100000;
  max:=8;
  for i:=1 to n-1 do
    max:=max*9 mod 12345;
  for i:=1 to n do
  begin
    if i mod 2=0 then begin
      t:=1;
      for j:=n downto n-i+1 do
      begin
        t:=t*j;
        if t>t2 then t:=t mod 2;
      end;
      for j:=i downto 2 do
      begin
        t:=t div j;
      end;
      max:=max+t;
      max:=max mod 12345;
    end;
  end;
  max:=max mod 12345;
  writeln(max);
  close(input);
  close(output);
end.