def Sq(l):
    s = 1
    for k in range(len(l)):
        if k%2==1:
            if l[k]%2==1:
                return 0
            s*=factorial(l[k])*((k+1)//2)**(l[k]//2)//factorial(l[k]//2)
        else:
            s*=sum(factorial(l[k])*(k+1)**i//factorial(i)//factorial(l[k]-2*i)//2**i for i in range(l[k]//2+1))
    return s

for n in range(1,30):
    s = 0
    for P in Partitions(n):
        P2 = P.to_exp()
        s += Sq(P2)*factorial(len(P))/prod(factorial(k) for k in P2)
    print(n,s)