Финальный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"C" Одиннадцатилетие
Ограничение по времени 4 секунды
Ограничение по памяти 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
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.