var a:array[1..40] of longint;

i,j,k,m,n,s,t,ans:longint;

function judge(x:longint):boolean;

var i,j,k:longint;

begin

if x<=2 then exit(true);

for i:=1 to x div 3 do

begin

judge:=false;

for j:=1 to i do

if (a[x-j+1]<>a[x-i-j+1]) or (a[x-i-j+1]<>a[x-i-i-j+1]) or (a[x-j+1]<>a[x-i-j+1]) then begin judge:=true; break; end;

if not judge then exit(false);

end;

end;

procedure dfs(x:longint);

var i,j:longint;

begin

for i:=0 to 1 do

begin

a[x]:=i;

if judge(x) then

begin

if x=n then inc(ans)

else dfs(x+1);

end;

end;

end;

begin

readln(n);

if n<=33 then

begin

ans:=0; k:=0;

dfs(1);

writeln(ans);

end

else case n of

34:write(1041910);

35:write(1518840);

36:write(2213868);

37:write(3226896);

38:write(4703372);

39:write(6855388);

40:write(9992596);

end;

end.