program zbfa;
var  i,j,n,s:integer;
     a:array[1..1000]of integer;
begin
     assign(input,'zbfa.in');
     assign(output,'zbfa.out');
     reset(input);
     rewrite(output);
     readln(n);
     a[1]:=1;
     for i:=2 to n+1 do begin
        a[i]:=1;
        for j:=i-1 downto 2 do begin
           a[j]:=a[j]+a[j-1];
           if a[j]>12345 then a[j]:=a[j] mod 12345;
        end;
     s:=-1;
     for i:=1 to n do begin
        s:=s+2*a[i];
        if s>12345 then s:=s mod 12345;
        end;
   end;
     writeln(s);
     close(input);
     close(output);
end.