program df;
var
f1,f2:text;
sum,n,a,i,d:integer;
procedure find(x:integer);
begin
a:=1;
for i:=1 to n-x-1 do  a:=a*9 mod 12345;
sum:=(sum-(8*(n-x)*a+9*a) mod 12345)mod 12345;
if x+2<n then find(x+2);
end;
begin
assign(f1,'chashu.in');
assign(f2,'chashu.out');
reset(f1);
rewrite(f2);
readln(f1,n);
close(f1);
if n=1 then begin writeln(f2,'9');close(f2);exit;end;
 sum:=9;
for i:= 1to n-1 do sum:=sum*10mod 12345;
find(1);
writeln(f2,sum);
close(f2);
end.