# First Try: Too Slow
# valid = [['O'], ['A'], ['L']]
# for i in xrange(20):
    # next = []
    # for p in valid:
        # next.append(p + ['O']) # adding an 'o' is always valid
        # if 'L' not in p:
            # next.append(p + ['L'])
        # if len(p) < 2 or p[-1] != 'A' or p[-2] != 'A':
            # next.append(p + ['A'])
    # valid = next
    # print len(valid)
    
# I suppose what we can do is classify codes into a couple 'buckets' based on their endings
# For each generation, every member of the bucket...
# O-never-L ... produces O-never-L, L, A-never-L
# O-has-L ... produces O-has-L, A-has-L
# A-has-L ... produces AA-has-L, O-has-L
# A-never-L ... produces AA-never-L, O-never-L, L
# AA-has-L ... produces O-has-L
# AA-never-L ... produces O-never-L, L
# L ... produces O-has-L, A-has-L

# This is ugly but not too different than a lot of other solutions (though other people did neat things with recursion)
# Using a hash here would've avoided the completely disgusting variable names in favor of only slightly disgusting hash keys
# Examination of the sequence also shows it to be a tribonacci sequence, so you could cheat and use that, too

# Seed first generation values
o_never_l = 1
o_has_l = 0
a_has_l = 0
a_never_l = 1
aa_has_l = 0
aa_never_l = 0
l = 1

for i in xrange(29):
    next_o_never_l = o_never_l + a_never_l + aa_never_l
    next_o_has_l = o_has_l + aa_has_l + a_has_l + l
    next_a_has_l = o_has_l + l
    next_a_never_l = o_never_l
    next_aa_has_l = a_has_l
    next_aa_never_l = a_never_l
    next_l = o_never_l + a_never_l + aa_never_l
    o_never_l, o_has_l, a_has_l, a_never_l, aa_has_l, aa_never_l, l = next_o_never_l, next_o_has_l, next_a_has_l, next_a_never_l, next_aa_has_l, next_aa_never_l, next_l
    print sum([o_never_l, o_has_l, a_has_l, a_never_l, aa_has_l, aa_never_l, l])