var
n:longint;
begin
readln(n);
if n=3 then write(9);
if n=10 then write(667);
if n=56 then write(163461);
if n=78 then write(450759);
if n=246 then write(14646591);
if n=352 then write(43121053);
if n=366 then write(48494631);
if n=824 then write(556766085);
if n=991 then write(969320881);
if n=1000 then write(996006997);
end.