CF856C Eleventh Birthday

今天是 Borya 的十一岁生日，他收到了一个很棒的礼物：$n$ 张写有数字的卡片，第 $i$ 张卡片上写着数字 $a_{i}$。Borya 想要将这些卡片排成一排，以得到一个更大的数字。例如，如果 Borya 拥有写有 $1$、$31$ 和 $12$ 的三张卡片，并按照这个顺序排列，他将得到数字 $13112$。 虽然 Borya 只有 11 岁，但他已经知道一共有 $n!$ 种排列方式。由于今天是一个特殊的日子，他只关心这样的排列方式，使得连接成的大数字能够被 $11$ 整除。比如上面的例子中 $13112=1192\times11$，所以这种方式是符合要求的。但如果顺序是 $31$、$1$、$12$，得到 $31112$，它不能被 $11$ 整除，这种方式就不符合要求。请你帮 Borya 计算，有多少种排卡片的好方法。 注意，对于 Borya，所有卡片都是不同的，即使有卡片上面的数字相同。例如，如果 Borya 有两张写着 $1$ 的卡片，也认为是两种不同的方法。 请帮 Borya 求出所有好的排列方式的数量。因为答案可能很大，请对 $998244353$ 取模后输出。

输入数据包含多个测试用例。第一行为整数 $t$，表示测试用例的数量（$1 \leq t \leq 100$）。接下来每个测试用例由两行描述。 第一行包含一个整数 $n$（$1 \leq n \leq 2000$），表示卡片的数量。 第二行包含 $n$ 个整数 $a_{i}$（$1 \leq a_{i} \leq 10^{9}$），表示每张卡片上的数字。 保证所有测试用例中卡片的总数不超过 $2000$。

对于每个测试用例，输出一行，表示将卡片排列使所得大数能被 $11$ 整除的合法方案数，对 $998244353$ 取模。

由 ChatGPT 5 翻译