Fan Service

A globally popular singer, Oh Youngsik, is holding a prize drawing during a concert. Each audience member has a ticket number of length 2K, and each position of the ticket number contains one of the given digits. The same digit may be used in multiple positions.

A ticket wins a prize if it satisfies at least one of the following two conditions.

1. The sum of the first K digits is equal to the sum of the last K digits.
2. Counting positions from the left, the sum of the digits in odd-numbered positions is equal to the sum of the digits in even-numbered positions.

Given K and the digits that may be used in ticket numbers, find the number of different ticket numbers that win a prize.

The first line contains a positive integer K, half of the ticket length. The full ticket length is 2K, and K <= 50.

The second line contains the digits that may be used, written without spaces. Each digit is between 0 and 9, and no digit appears more than once.

Print the number of winning ticket numbers modulo 999983.

When K = 2 and the usable digits are 2 and 1, the winning ticket numbers are 1111, 1122, 1212, 1221, 2112, 2121, 2211, 2222.