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

LuckyTicket(2) ➞ 10

LuckyTicket(4) ➞ 670

LuckyTicket(12) ➞ 39581170420

Notes

• There are checks for n > 10, so watch out for code performance.
• If you have problems finding a productive algorithm, look in the comments, there is one good person who explained the solution algorithm.