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(i):
if i==len(ans):
return
print(int(ans[i]))
prnt(i+1)
def check(s,i):
if i>=len(s)-1:
return True
if s[i] in '024' and s[i+1] in '024':
return False
return check(s,i+1)
def rec2(s,n):
global cnt
if n==0:
if check(s,0):
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(0)
cnt=0
rec2('',N)
print(cnt)