Fan Service

Time limit2sMemory limit128 MB

Summary

Count length-2K ticket numbers over a given digit set where the two halves have equal digit sums or the odd/even positions have equal digit sums, modulo 999983.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

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.

The sum of the first K digits is equal to the sum of the last K digits.
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.

Input

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.

Output

Print the number of winning ticket numbers modulo 999983.

Hint

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

Examples5

Example 1
Input
```
2
21
```
Expected output
```
8
```
Example 2
Input
```
1
0123456789
```
Expected output
```
10
```
Example 3
Input
```
2
0123456789
```
Expected output
```
1240
```
Example 4
Input
```
10
731
```
Expected output
```
207444
```
Example 5
Input
```
50
0123456789
```
Expected output
```
367584
```