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.