#!/usr/bin/env python3

# p  -> recursive with lookup table
# p2 -> count individual combs, add squares, got from forum

def p(n, tbl=False):
    if n < 3:
        return 1
    if tbl==False:
        tbl = []
    if n-3 >= len(tbl):
        r = 2*p(n-1, tbl) - p(n-2,tbl) + p(n-4, tbl)
        tbl.append(r)
    return tbl[n-3]

def p2(n):
    if n < 3:
        return 1
    rd = 1
    b1 = b2 = 0
    b3 = 1
    for i in range(3,n):
        b = b3
        b3 += b2
        b2  = b1
        b1  = rd
        rd += b
    return rd+b1+b2+b3

print(p(50))