Number of Lucky Tickets

Create a function that counts how many n-digit numbers have the same sum of the first half and second half of the digits (“lucky” numbers). The number n is even. For example, for n = 6, the numbers "001010", "112220", "000000" are lucky.

Examples

lucky_ticket(2) ➞ 10

lucky_ticket(4) ➞ 670

lucky_ticket(12) ➞ 39581170420

Notes

• The function should be really efficient.
• The runtime increases 10 fold per test. Just for information: my solution takes 6 seconds, which is still under the server time-limit, so you are good to go.