在n个连续的方格内填写字母A或B，相邻两格不能同时都填B。求所有可能的填写方案数。

一个整数n

按从小到输出每行的字符串，一个字符串一行

最后一行表示总的方案数

n <20

n = int( input( ) )
a = [ 0 ] * n
sum = 0
for i in range( _____(1)_____ ):
    r = "";     m = i
    for j in range( n ):
      _____(2)______
      m = m//2
    flag = True
    for j in range( 1, n ):
        if _________(3)__________: flag = False
    if flag:
        for j in range( n ):
            if a[j] == 0:
                r = "A" + r
            else:
                r = "B" + r
        print( r )
        sum += 1

print( sum )