Eleventh Birthday
Contest: Russian Code Cup 2017 - Finals [Unofficial Mirror, Div. 1 Only Recommended, Teams Allowed]
Difficulty rating: 2400
Tags: combinatorics, dp, math

It is Borya's eleventh birthday, and he has got a great present: n cards with numbers. The i-th card has the number ai written on it. Borya wants to put his cards in a row to get one greater number. For example, if Borya has cards with numbers 1, 31, and 12, and he puts them in a row in this order, he would get a number 13112.

He is only 11, but he already knows that there are n! ways to put his cards in a row. But today is a special day, so he is only interested in such ways that the resulting big number is divisible by eleven. So, the way from the previous paragraph is good, because 13112 = 1192 × 11, but if he puts the cards in the following order: 31, 1, 12, he would get a number 31112, it is not divisible by 11, so this way is not good for Borya. Help Borya to find out how many good ways to put the cards are there.

Borya considers all cards different, even if some of them contain the same number. For example, if Borya has two cards with 1 on it, there are two good ways.

Help Borya, find the number of good ways to put the cards. This number can be large, so output it modulo 998244353.

Input format:
Input data contains multiple test cases. The first line of the input data contains an integer t — the number of test cases (1 ≤ t ≤ 100). The descriptions of test cases follow.

Each test is described by two lines.

The first line contains an integer n (1 ≤ n ≤ 2000) — the number of cards in Borya's present.

The second line contains n integers ai (1 ≤ ai ≤ 109) — numbers written on the cards.

It is guaranteed that the total number of cards in all tests of one input data doesn't exceed 2000.

Output format:
For each test case output one line: the number of ways to put the cards to the table so that the resulting big number was divisible by 11, print the number modulo 998244353.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
4
2
1 1
3
1 31 12
3
12345 67 84
9
1 2 3 4 5 6 7 8 9

Example output:
2
2
2
31680

Editorial:
Let us use divisibility rule for eleven. The number is divisible by eleven if the sum of digits at odd positions is equal to the sum of digits at even positions modulo 11. So for each number on a card there are only two parameters that we care about: the sign interchanging sum of its digits with digits at odd positions positive and digits at even position negative, and the parity of its digit count.
Let us divide all cards to two groups: with even digit count and with odd digit count. Let us first put cards with numbers that have odd count of digits. Half of them (rounded up) will have their sign interchanging sum used as positive, other half as negative. Let us use dynamic programming to find the number of ways to sum them up to have a given sum modulo 11. The state includes the number of cards considered, the number of cards that are used as positive, and the current sum modulo 11. There are two transitions: take the current card as positive, and take it as negative.
If there are no cards with odd digit count, no matter how you order even digit count cards the result modulo 11 is the same. So the answer is either 0 or n!. In the other case each even digit count card can be used either as positive, or as negative, independent of the other cards. Use analogous dynamic programming to count the number of ways to get each possible sum modulo 11.
Finally, combine results for even and odd digit count cards, getting the total sum modulo 11 equal to 0.
Time complexity is O(n2).