Счастливые билетики

Напишите функцию, которая считает, сколько существует «счастливых» чисел длины n.

Счастливым считается число, у которого сумма цифр в левой части равна сумме цифр в правой части.

Например, при n = 6 «счастливыми» будут такие числа: 001010, 112220, 000000.

Примеры

lucky_ticket(2) ➞ 10

lucky_ticket(4) ➞ 670

lucky_ticket(12) ➞ 39581170420

Примечание

• n — гарантированно четное число.
• В этой задаче придется попотеть, потому что функция должна быть максимально оптимизирована.