C. Одиннадцатилетие
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На одиннадцатый день рождения Боре подарили n карточек с числами. На i-й карточке написано число ai. Боря хочет выложить карточки в один ряд так, чтобы получилось одно большое число. Например, если у Бори есть карточки с числами 1, 31 и 12, и он выложит их в этом порядке, он получит число 13112.

В свои 11 он уже знает, что всего существует n! способов вызложить карточки, но сегодня его интересуют только те способы, в результате которых, он получит число, которое делится на одиннадцать. Так, приведенный выше способ подходит, поскольку 13112 = 1192 × 11, а вот если он выложит карточки в последовательности 31, 1, 12, то он получит число 31112, которое не делится на 11, этот способ Боре не подходит. Помогите Боре посчитать количество таких способов.

Даже если на двух карточках написаны одинаковые числа, Боря считает способы, которые отличаются обменом этих двух карточек, различными, например, если у Бори есть две карточки с числом 1, то он может выложить их на стол двумя способами.

Помогите Боре, найдите число подходящих способов выложить карточки. Поскольку это количество может быть слишком большим, требуется вывести остаток от его деления на 998244353.

Входные данные

Входные данные содержат несколько тестов. Первая строка входных данных содержит число t — количество тестов (1 ≤ t ≤ 100). Далее следуют описания тестов.

Каждый тест описывается двумя строками.

Первая из них содержит целое число n (1 ≤ n ≤ 2000) — количество карточек, которое подарили Боре.

Вторая строка содержит n чисел ai (1 ≤ ai ≤ 109) — числа, которые записаны на карточках.

Гарантируется, что суммарное количество карточек во всех тестах одних входных данных не превышает 2000.

Выходные данные

Для каждого теста в отдельной строке выведите остаток от деления на 998244353 количества способов выложить карточки таким образом, чтобы получившееся число делилось на 11.

Пример
Входные данные
4
2
1 1
3
1 31 12
3
12345 67 84
9
1 2 3 4 5 6 7 8 9
Выходные данные
2
2
2
31680