from copy import *

def happy(ticketNumber):
    k = len(ticketNumber)
    n = k // 2
    s0 = 0
    for i in range(0, n):
        s0 += ticketNumber[i]
    s1 = 0
    for i in range(n, k):
        s1 += ticketNumber[i]
    return (s0 == s1)
    
def happyTickets(k):
    n = 0
    res = []
    numSteps = 100
    if k >= 8:
        numSteps = 1000
    currentNumber = [0]*k
    initialNumber = currentNumber.copy()
    if happy(currentNumber):
        res.append(currentNumber)
    next(currentNumber)
    while currentNumber != initialNumber:
        if happy(currentNumber):
            res.append(currentNumber.copy())
            n += 1
            if n%numSteps == 0:
                print(".", end="", flush=True)
        next(currentNumber)
    print("")
    return res
    
def next(ticketNumber):
    k = len(ticketNumber)
    i = k - 1
    while i >= 0:
        if ticketNumber[i] < 9:
            ticketNumber[i] += 1
            break
        else:
            ticketNumber[i] = 0
            i -= 1
            
def numHappyTickets(n):
    k = n // 2
    maxSum = 9*k
    sums = [0]*(maxSum + 1)
    number = [0]*k
    initialNumber = number.copy()
    while True:
        s = sum(number)
        sums[s] += 1
        next(number)
        if number == initialNumber:
            break
    res = 0
    for s in sums:
        res += s*s
    return res