program mason;
var
f1,f2:text;
p,d:longint;
x:array[1..501]of integer;
y:array[1..1000]of integer;
procedure step(m:longint);
var
i,j:longint;
begin
if m=0 then exit;
step(m div 2);
for i:=1 to 500 do
 for j:=1 to 500 do
 if m mod 2=0 then y[i+j-1]:=x[i]*x[j]+y[i+j-1]
 else y[i+j-1]:=x[i]*x[j]*2+y[i+j-1];
for i:=1 to 500 do
 begin
 x[i]:=y[i] mod 10;
 y[i+1]:=(y[i] div 10)+y[i+1];
 end;
fillchar(y,sizeof(y),0);
end;

procedure print;
var
i:longint;
begin
for i:=500 downto 1 do
begin
if i<>1 then
write(f2,x[i])
else write(f2,x[1]-1);
if (i<>500)and(i mod 50=1) then writeln(f2);
end;
close(f1);
close(f2);
end;

begin
assign(f1,'mason.in');
reset(f1);
assign(f2,'mason.out');
rewrite(f2);
read(f1,p);
d:=trunc(ln(2)/ln(10)*p+1);
writeln(f2,d);
x[1]:=1;
step(p);
print;
end.