{"problem":{"name":"C. Eleventh Birthday","description":{"content":"It is Borya's eleventh birthday, and he has got a great present: _n_ cards with numbers. The _i_\\-th card has the number _a__i_ written on it. Borya wants to put his cards in a row to get one greater ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF856C"},"statements":[{"statement_type":"Markdown","content":"It is Borya's eleventh birthday, and he has got a great present: _n_ cards with numbers. The _i_\\-th card has the number _a__i_ written on it. Borya wants to put his cards in a row to get one greater number. For example, if Borya has cards with numbers 1, 31, and 12, and he puts them in a row in this order, he would get a number 13112.\n\nHe is only 11, but he already knows that there are _n_! ways to put his cards in a row. But today is a special day, so he is only interested in such ways that the resulting big number is divisible by eleven. So, the way from the previous paragraph is good, because 13112 = 1192 × 11, but if he puts the cards in the following order: 31, 1, 12, he would get a number 31112, it is not divisible by 11, so this way is not good for Borya. Help Borya to find out how many good ways to put the cards are there.\n\nBorya considers all cards different, even if some of them contain the same number. For example, if Borya has two cards with 1 on it, there are two good ways.\n\nHelp Borya, find the number of good ways to put the cards. This number can be large, so output it modulo 998244353.\n\n## Input\n\nInput data contains multiple test cases. The first line of the input data contains an integer _t_ — the number of test cases (1 ≤ _t_ ≤ 100). The descriptions of test cases follow.\n\nEach test is described by two lines.\n\nThe first line contains an integer _n_ (1 ≤ _n_ ≤ 2000) — the number of cards in Borya's present.\n\nThe second line contains _n_ integers _a__i_ (1 ≤ _a__i_ ≤ 109) — numbers written on the cards.\n\nIt is guaranteed that the total number of cards in all tests of one input data doesn't exceed 2000.\n\n## Output\n\nFor each test case output one line: the number of ways to put the cards to the table so that the resulting big number was divisible by 11, print the number modulo 998244353.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Borya 度过了他的十一岁生日，收到了一份很棒的礼物：#cf_span[n] 张写有数字的卡片。第 #cf_span[i] 张卡片上写着数字 #cf_span[ai]。Borya 想把这些卡片排成一行，组成一个尽可能大的数。例如，如果 Borya 有数字为 #cf_span[1]、#cf_span[31] 和 #cf_span[12] 的卡片，他按此顺序排列，会得到数字 #cf_span[13112]。\n\n他才 11 岁，但他已经知道有 #cf_span[n!] 种方式将卡片排成一行。但今天是个特殊的日子，他只关心那些最终组成的大数能被 11 整除的排列方式。因此，上一段中的排列是可行的，因为 #cf_span[13112 = 1192 × 11]；但如果他按 #cf_span[31]、#cf_span[1]、#cf_span[12] 的顺序排列，则得到数字 #cf_span[31112]，它不能被 #cf_span[11] 整除，因此这种方式对 Borya 不合适。请帮助 Borya 计算有多少种合适的排列方式。\n\nBorya 认为所有卡片都是不同的，即使其中一些卡片上的数字相同。例如，如果 Borya 有两张写有 1 的卡片，则存在两种合适的排列方式。\n\n请帮助 Borya 计算合适的排列方式的数量。这个数可能很大，请对 #cf_span[998244353] 取模后输出。\n\n输入数据包含多个测试用例。输入的第一行包含一个整数 #cf_span[t] —— 测试用例的数量（#cf_span[1 ≤ t ≤ 100]）。接下来是各个测试用例的描述。\n\n每个测试用例由两行组成。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2000]）—— Borya 礼物中卡片的数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[1 ≤ ai ≤ 10^9]）—— 卡片上写的数字。\n\n保证所有测试用例中卡片总数不超过 #cf_span[2000]。\n\n对于每个测试用例，输出一行：将卡片排成一行使得组成的大数能被 11 整除的方案数，结果对 #cf_span[998244353] 取模。\n\n## Input\n\n输入数据包含多个测试用例。输入的第一行包含一个整数 #cf_span[t] —— 测试用例的数量（#cf_span[1 ≤ t ≤ 100]）。接下来是各个测试用例的描述。每个测试用例由两行组成。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2000]）—— Borya 礼物中卡片的数量。第二行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[1 ≤ ai ≤ 10^9]）—— 卡片上写的数字。保证所有测试用例中卡片总数不超过 #cf_span[2000]。\n\n## Output\n\n对于每个测试用例，输出一行：将卡片排成一行使得组成的大数能被 11 整除的方案数，结果对 #cf_span[998244353] 取模。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n $ be the number of cards, and let $ a_i \\in \\mathbb{Z}^+ $ be the number written on the $ i $-th card ($ 1 \\leq i \\leq n $).\n\nEach card is distinct (even if values repeat), so we consider all $ n! $ permutations of the cards.\n\nFor a permutation $ \\pi \\in S_n $, let $ N_\\pi $ denote the integer formed by concatenating the decimal representations of $ a_{\\pi(1)}, a_{\\pi(2)}, \\dots, a_{\\pi(n)} $ in that order.\n\nWe are to count the number of permutations $ \\pi $ such that:\n\n$$\nN_\\pi \\equiv 0 \\pmod{11}\n$$\n\n---\n\n### Key Insight: Divisibility by 11\n\nA number is divisible by 11 if and only if the alternating sum of its digits is divisible by 11.\n\nHowever, since we are concatenating entire numbers (not digits), we use the following property:\n\nLet $ x $ be a number with decimal representation $ d_k d_{k-1} \\dots d_0 $. Then:\n\n$$\nx \\equiv \\sum_{i=0}^k d_i \\cdot (-1)^i \\pmod{11}\n$$\n\nThus, for a concatenated number formed by numbers $ b_1, b_2, \\dots, b_n $, we can compute its value modulo 11 as:\n\n$$\n\\sum_{j=1}^n \\left( b_j \\cdot (-1)^{s_j} \\right) \\pmod{11}\n$$\n\nwhere $ s_j $ is the total number of digits in all numbers to the *right* of $ b_j $ (i.e., the position offset from the right end).\n\nLet $ L_j = \\text{number of digits in } a_j $.\n\nThen, if $ a_j $ is placed at position $ i $ (from left) in the permutation, then the number of digits to its right is:\n\n$$\nR = \\sum_{k \\text{ after } j} L_k\n$$\n\nSo the contribution of $ a_j $ to the total alternating sum modulo 11 is:\n\n$$\na_j \\cdot (-1)^R \\pmod{11}\n$$\n\nNote: $ (-1)^R = (-1)^{\\sum_{k \\text{ after } j} L_k} = \\prod_{k \\text{ after } j} (-1)^{L_k} $\n\nSo define for each card $ j $:\n\n- $ d_j = \\text{number of digits of } a_j $\n- $ c_j = a_j \\mod 11 $\n- $ \\sigma_j = (-1)^{d_j} \\in \\{1, -1\\} $\n\nThen, if we fix an ordering $ \\pi $, the total alternating sum modulo 11 is:\n\n$$\n\\sum_{i=1}^n c_{\\pi(i)} \\cdot \\prod_{k=i+1}^n \\sigma_{\\pi(k)} \\pmod{11}\n$$\n\nLet $ P_i = \\prod_{k=i+1}^n \\sigma_{\\pi(k)} $. Then $ P_i = P_{i+1} \\cdot \\sigma_{\\pi(i+1)}^{-1} $, and $ P_n = 1 $.\n\nAlternatively, define a **state** as the cumulative product of $ \\sigma $'s from the end.\n\nLet’s define:\n\n- Let $ \\tau_j = (-1)^{d_j} $ (i.e., $ \\sigma_j $)\n- Let $ S = \\prod_{j=1}^n \\tau_j $ — the total sign product over all cards.\n\nThen, if we place card $ j $ at position $ i $, and let $ T_i $ be the product of $ \\tau $'s of all cards to the *right* of position $ i $, then:\n\n$$\n\\text{Contribution of card } j \\text{ at position } i = c_j \\cdot T_i\n$$\n\nBut $ T_i $ depends on which cards are to the right — so we need to track the **product of $ \\tau $'s for the suffix**.\n\nThis suggests a **dynamic programming** approach:\n\n---\n\n### Formal DP Formulation\n\nLet:\n\n- $ n $: number of cards\n- For each card $ i $, define:\n  - $ d_i = \\lfloor \\log_{10}(a_i) \\rfloor + 1 $ (number of digits)\n  - $ \\tau_i = (-1)^{d_i} \\in \\{1, -1\\} $\n  - $ c_i = a_i \\mod 11 $\n\nWe want to count the number of permutations $ \\pi $ such that:\n\n$$\n\\sum_{i=1}^n c_{\\pi(i)} \\cdot \\left( \\prod_{j=i+1}^n \\tau_{\\pi(j)} \\right) \\equiv 0 \\pmod{11}\n$$\n\nLet’s define DP state:\n\n- $ \\text{dp}[i][s][r] $ = number of ways to assign the first $ i $ cards (in some order) such that:\n  - $ s $ is the **product of $ \\tau $'s** of the remaining (unplaced) cards (i.e., the suffix product multiplier),\n  - $ r $ is the **current alternating sum modulo 11** contributed by the placed cards.\n\nWait — better idea: process cards one by one and build the permutation from **right to left**.\n\n### Better: Process from Right to Left\n\nLet’s build the number from right to left (i.e., place cards in reverse order). Then the rightmost card has exponent $ (-1)^0 = 1 $, the one to its left has $ (-1)^{d_{\\text{right}}} $, etc.\n\nDefine:\n\n- Let $ \\text{dp}[mask][prod][sum] $ be the number of ways to assign cards corresponding to bitmask $ mask $, such that:\n  - $ prod $ is the product of $ \\tau $'s of all cards **already placed** (i.e., to the right of the current position) — this will be the multiplier for the next card to the left.\n  - $ sum $ is the current total alternating sum modulo 11.\n\nBut $ n \\leq 2000 $, so bitmask is impossible.\n\nAlternative insight: since $ \\tau_i \\in \\{1, -1\\} $, the product of any subset is also $ \\pm 1 $. So $ prod \\in \\{1, -1\\} $, and $ sum \\in \\mathbb{Z}_{11} $.\n\nSo we can use DP over:\n\n- $ \\text{dp}[i][p][r] $: number of ways to assign $ i $ cards such that the product of $ \\tau $'s of the assigned cards is $ p \\in \\{1, -1\\} $, and the total alternating sum mod 11 is $ r $.\n\nWait — no. The multiplier for a card placed now depends on the **product of $ \\tau $'s of cards already placed to its right**.\n\nSo if we build the permutation from **right to left**, then:\n\n- Start with no cards placed: product = 1, sum = 0\n- When we place a card $ j $ to the left of the current sequence:\n  - Its contribution: $ c_j \\cdot (\\text{current product}) $\n  - Then update product: $ \\text{new product} = \\text{current product} \\cdot \\tau_j $\n  - Update sum: $ \\text{new sum} = (\\text{current sum} + c_j \\cdot \\text{current product}) \\mod 11 $\n\nSo state:\n\n- $ \\text{dp}[i][p][r] $: number of ways to have placed $ i $ cards, with the product of $ \\tau $'s of the placed cards being $ p \\in \\{1, -1\\} $, and total alternating sum mod 11 being $ r \\in \\{0,1,\\dots,10\\} $\n\nWe iterate over all cards, and for each unplaced card, we try placing it to the left.\n\nBut we have $ n \\leq 2000 $, and $ p \\in \\{1, -1\\} $, $ r \\in \\mathbb{Z}_{11} $, so state space is $ O(n \\cdot 2 \\cdot 11) = O(44000) $, which is acceptable.\n\nBut we need to account for **identical values**: since cards are distinct, we must consider each card individually, even if values are same.\n\nSo we need to iterate over all cards and use DP over subsets? No — we can use DP that doesn’t care which card, but counts multiplicities.\n\nActually, we can group cards by $ (d_i, a_i \\mod 11) $, i.e., by $ (\\tau_i, c_i) $.\n\nLet’s define:\n\n- Group cards by type: each type is a pair $ (\\tau, c) $, where $ \\tau \\in \\{1, -1\\} $, $ c \\in \\{0,1,\\dots,10\\} $\n- Let $ f[\\tau][c] $ be the count of cards of type $ (\\tau, c) $\n\nThen we can do DP over:\n\n- $ \\text{dp}[p][r] $: number of ways to assign a multiset of cards (with counts reduced) such that:\n  - $ p \\in \\{1, -1\\} $: product of $ \\tau $'s of all cards already placed (to the right)\n  - $ r \\in \\mathbb{Z}_{11} $: current alternating sum mod 11\n\nWe iterate over all card types, and for each type, we decide how many cards of that type to place, and in what order? No — since the order of placing cards of the same type doesn’t matter in terms of state, but we need to account for permutations.\n\nActually, since cards are distinct, we must account for **which specific card** is placed, but if two cards have same $ (\\tau, c) $, they are interchangeable in terms of state transition.\n\nSo we can do:\n\nLet $ \\text{dp}[p][r] $ be the number of ways to assign a subset of cards (with multiplicity) such that the product of $ \\tau $'s of placed cards is $ p $, and the sum is $ r $. We process cards one by one, and for each card, we can choose to place it next (to the left), updating state.\n\nBut since total $ n \\leq 2000 $, and we have up to 2000 cards, and state is $ 2 \\times 11 = 22 $, we can do DP over cards:\n\nInitialize: $ \\text{dp}[1][0] = 1 $\n\nFor each card $ i $ (from 1 to $ n $), we update:\n\nNew state: for each existing state $ (p, r) $, we can place card $ i $ to the left of the current sequence.\n\nThen:\n\n- New product: $ p' = p \\cdot \\tau_i $\n- New sum: $ r' = (r + c_i \\cdot p) \\mod 11 $\n\nAnd we add $ \\text{dp}[p][r] $ to $ \\text{dp}[p'][r'] $\n\nBut this assumes we are building the permutation one card at a time, and each card is used exactly once.\n\nThis is **correct** and the state space is $ O(n \\cdot 2 \\cdot 11) = O(44000) $, which is acceptable for $ n \\leq 2000 $.\n\nBut note: the order of processing cards matters? No — we are iterating over all cards, and each card is used once. Since the transition is linear and we process each card once, this is equivalent to counting all permutations.\n\nWait — no: in this DP, we are **not** accounting for the fact that we are building permutations — we are just accumulating the total number of ways to assign cards in some order. But since we are considering each card exactly once, and we are updating the state by placing the next card to the left, this DP naturally counts **all permutations**.\n\nYes: the recurrence is:\n\n$$\n\\text{dp}_{\\text{new}}[p \\cdot \\tau_i][(r + c_i \\cdot p) \\mod 11] \\mathrel{+}= \\text{dp}_{\\text{old}}[p][r]\n$$\n\nfor each card $ i $, and we start with one state and add cards one by one.\n\nThis is **exactly** the standard DP for counting permutations with state, and it gives the total number of permutations satisfying the condition.\n\nBut we must process cards **one by one**, and for each card, we update the entire state table.\n\nAlgorithm:\n\n- Initialize: $ \\text{dp}[1][0] = 1 $\n- For each card $ i = 1 $ to $ n $:\n  - Create new_dp = copy of current dp\n  - For each state $ (p, r) $ in current dp:\n    - Let $ \\tau = \\tau_i $, $ c = c_i $\n    - New product: $ p' = p \\cdot \\tau $\n    - New sum: $ r' = (r + c \\cdot p) \\mod 11 $\n    - Add $ \\text{dp}[p][r] $ to $ \\text{new\\_dp}[p'][r'] $\n  - Set $ \\text{dp} = \\text{new\\_dp} $\n\nWait — this is **incorrect**. Why? Because we are not choosing *which* card to place next — we are forcing an order of processing. But we want to count **all permutations**, so we need to consider that each card is placed in some position.\n\nActually, the above DP **does** count all permutations, because we are iterating over all cards and for each card, we are inserting it at the **left end** of the current sequence. Since every permutation can be built by successively inserting cards at the left, and the state captures the cumulative effect, this is correct.\n\nBut note: the transition assumes we are placing the card to the left of the current sequence. Since the multiplier for the new card is the product of $ \\tau $'s of the cards already placed (to its right), this is exactly what we need.\n\nAnd since we process all cards, and each card is used once, the total number of sequences built is $ n! $, and the DP counts each permutation exactly once.\n\nTherefore, the final answer is $ \\text{dp}[p][0] $ for any $ p \\in \\{1, -1\\} $, because we only care that the total sum mod 11 is 0.\n\nBut note: we don't care about the final product $ p $, only the sum.\n\nSo:\n\n$$\n\\boxed{\\text{Answer} = \\left( \\text{dp}[1][0] + \\text{dp}[-1][0] \\right) \\mod 998244353}\n$$\n\nWe must handle $ -1 \\mod 11 $ as 10, but in our state, we can store $ p \\in \\{1, 10\\} $ (since $ -1 \\equiv 10 \\mod 11 $), but actually for $ p $, we are multiplying integers, so we can store $ p \\in \\{1, -1\\} $ as integers, and do arithmetic mod 11 only for the sum.\n\nIn code, we can represent $ p $ as 1 or -1 (integers), and do:\n\n- $ p' = p \\cdot \\tau_i $ → result is $ \\pm 1 $\n- $ r' = (r + c_i \\cdot p) \\mod 11 $\n\nWe'll use a 2D DP array: $ \\text{dp}[2][11] $, where index 0 for $ p=1 $, index 1 for $ p=-1 $\n\nInitialize: $ \\text{dp}[0][0] = 1 $\n\nFor each card $ i $:\n\n- Let $ \\tau = (-1)^{d_i} $, $ c = a_i \\mod 11 $\n- Create new_dp[2][11] = {0}\n- For each $ p\\_idx \\in \\{0,1\\} $, $ r \\in 0..10 $:\n  - If $ \\text{dp}[p\\_idx][r] > 0 $:\n    - $ p = 1 $ if $ p\\_idx == 0 $, else $ -1 $\n    - $ new\\_p = p \\cdot \\tau $\n    - $ new\\_p\\_idx = 0 $ if $ new\\_p == 1 $, else 1\n    - $ new\\_r = (r + c \\cdot p) \\mod 11 $\n    - $ \\text{new\\_dp}[new\\_p\\_idx][new\\_r] \\mathrel{+}= \\text{dp}[p\\_idx][r] $\n- Set $ \\text{dp} = \\text{new\\_dp} $\n\nAfter all cards, answer = $ (\\text{dp}[0][0] + \\text{dp}[1][0]) \\mod 998244353 $\n\nThis is efficient: $ O(n \\cdot 2 \\cdot 11) = O(22n) \\leq 44000 $ per test case.\n\nTotal cards across test cases ≤ 2000, so total operations ≤ 2000 * 22 = 44000 — very feasible.\n\n---\n\n### Final Mathematical Formulation\n\nLet $ n \\in \\mathbb{N} $, and for $ i = 1, \\dots, n $, let:\n\n- $ d_i = \\lfloor \\log_{10}(a_i) \\rfloor + 1 $\n- $ \\tau_i = (-1)^{d_i} \\in \\{1, -1\\} $\n- $ c_i = a_i \\mod 11 \\in \\{0, 1, \\dots, 10\\} $\n\nLet $ \\text{dp}[p][r] $ be the number of ways to assign a subset of cards (processed so far) such that:\n\n- $ p \\in \\{1, -1\\} $: the product of $ \\tau $'s of the placed cards (i.e., the multiplier for the next card to the left)\n- $ r \\in \\mathbb{Z}_{11} $: the current alternating sum mod 11\n\nInitialize: $ \\text{dp}[1][0] = 1 $, all others 0.\n\nFor each card $ i = 1 $ to $ n $:\n\n$$\n\\text{new\\_dp}[p \\cdot \\tau_i][(r + c_i \\cdot p) \\mod 11] \\mathrel{+}= \\text{dp}[p][r] \\quad \\forall p \\in \\{1, -1\\}, r \\in \\mathbb{Z}_{11}\n$$\n\nThen, the answer is:\n\n$$\n\\left( \\text{dp}[1][0] + \\text{dp}[-1][0] \\right) \\mod 998244353\n$$\n\nThis counts the number of permutations of the $ n $ cards such that the concatenated number is divisible by 11.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF856C","tags":["combinatorics","dp","math"],"sample_group":[["4\n2\n1 1\n3\n1 31 12\n3\n12345 67 84\n9\n1 2 3 4 5 6 7 8 9","2\n2\n2\n31680"]],"created_at":"2026-03-03 11:00:39"}}