← 返回题目列表

Codeforces · 856/C

C. 十一岁生日

中文机器翻译题面 查看原题

今天是 Borya 的十一岁生日,他收到了一份很棒的礼物:n 张带有数字的卡片。第 i 张卡片上写着数字 ai。博里亚想要将他的牌排成一排,以获得更大的数字。例如,如果 Borya 有数字为 1、31 和 12 的牌,他将它们按此顺序排成一行,他将得到数字 13112。

他只有11岁,但他已经知道有n个!把他的牌排成一排的方法。但今天是个特殊的日子,所以他只对得到的大数能被11整除的方式感兴趣。所以,上一段的方法是好的,因为 13112 = 1192 × 11,但是如果他按照以下顺序放置卡片:31,1,12,他会得到一个数字 31112,它不能被 11 整除,所以这种方法对 Borya 来说不好。帮助 Borya 找出有多少种放置卡片的好方法。

Borya 认为所有卡牌都是不同的,即使其中一些卡牌包含相同的数字。例如,如果 Borya 有两张牌,上面有 1,那么有两种好方法。

帮助Borya,找到放置卡片数量的好方法。该数字可能很大,因此输出它对 998244353 求模。

输入

输入数据包含多个测试用例。输入数据的第一行包含一个整数 t - 测试用例的数量 (1 ≤ t ≤ 100)。测试用例的描述如下。

每个测试由两行描述。

第一行包含一个整数 n (1 ≤ n ≤ 2000) — Borya 手中的卡片数量。

第二行包含 n 个整数 ai (1 ≤ ai ≤ 109) — 写在卡片上的数字。

保证一次输入数据所有测试的卡牌总数不超过2000张。

输出

对于每个测试用例输出一行:将卡片放到桌子上的方式数,以便得到的大数字可以被 11 整除,打印该数字模 998244353。

示例

输入 #1

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

输出 #1

2
2
2
31680