今天是 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