def rec(s,n):
global ans
if n==0:
ans.append(s)
return
rec(s+'0',n-1)
rec(s+'1',n-1)
rec(s+'2',n-1)
rec(s+'3',n-1)
def prnt_rev(i):
if i<0:
return
print(int(ans[i]))
prnt_rev(i-1)
def rec2(s,n):
global cnt
if n==0:
ok=True
for i in range(len(s)-1):
if s[i] in '13' and s[i+1] in '13':
ok=False
break
if ok:
cnt+=1
return
rec2(s+'0',n-1)
rec2(s+'1',n-1)
rec2(s+'2',n-1)
rec2(s+'3',n-1)
N=int(input())
ans=[]
rec('',N)
prnt_rev(len(ans)-1)
cnt=0
rec2('',N)
print(cnt)