{"problem":{"name":"Minimization of Divide","description":{"content":"You are given two length-$N$ sequences of non-negative integers: $A=(A_1,A_2,\\dots,A_N)$ and $B=(B_1,B_2,\\dots,B_N)$. For a permutation $P=(P_1,P_2,\\dots,P_N)$ of $(1,2,\\dots,N)$, define the cost of $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc075_c"},"statements":[{"statement_type":"Markdown","content":"You are given two length-$N$ sequences of non-negative integers: $A=(A_1,A_2,\\dots,A_N)$ and $B=(B_1,B_2,\\dots,B_N)$.\nFor a permutation $P=(P_1,P_2,\\dots,P_N)$ of $(1,2,\\dots,N)$, define the cost of $P$ as $\\sum_{i=1}^{N} \\left \\lfloor \\frac{A_{P_i}}{2^{B_i}} \\right \\rfloor$.\nFind the number, modulo $998244353$, of permutations $P$ that achieve the minimum cost.\nYou are given $T$ test cases; solve each of them.\n\n## Constraints\n\n*   $1 \\le T \\le 2 \\times 10^5$\n*   $1 \\le N \\le 2 \\times 10^5$\n*   $1 \\le A_i \\le 10^9$\n*   $0 \\le B_i \\le 30$\n*   The sum of $N$ over all test cases is at most $2 \\times 10^5$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach test case is given in the following format:\n\n$N$\n$A_1\\ A_2\\ \\dots\\ A_N$\n$B_1\\ B_2\\ \\dots\\ B_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc075_c","tags":[],"sample_group":[["7\n2\n5 9\n0 1\n3\n3 4 10\n0 1 2\n4\n1 2 3 4\n0 0 1 1\n5\n1000000000 1000000000 1000000000 1000000000 1000000000\n0 0 0 0 0\n11\n19 68 97 62 99 52 57 19 43 80 96\n5 3 3 2 3 4 3 2 3 4 3\n14\n86 49 83 31 5 43 7 46 98 36 60 4 69 59\n3 1 4 4 4 0 1 3 0 4 3 5 1 2\n10\n907139744 237517128 852012347 350549430 62876062 196019710 263351472 184393437 281593038 753973502\n23 12 1 26 29 24 0 7 10 4","1\n2\n4\n120\n8640\n15552\n1\n\nFor the first test case, the cost for each $P$ is as follows:\n\n*   For $P=(1,2)$, $\\left \\lfloor \\frac{A_{1}}{2^{B_1}} \\right \\rfloor + \\left \\lfloor \\frac{A_{2}}{2^{B_2}} \\right \\rfloor = \\left \\lfloor \\frac{5}{1} \\right \\rfloor + \\left \\lfloor \\frac{9}{2} \\right \\rfloor = 9$\n*   For $P=(2,1)$, $\\left \\lfloor \\frac{A_{2}}{2^{B_1}} \\right \\rfloor + \\left \\lfloor \\frac{A_{1}}{2^{B_2}} \\right \\rfloor = \\left \\lfloor \\frac{9}{1} \\right \\rfloor + \\left \\lfloor \\frac{5}{2} \\right \\rfloor = 11$\n\nThus, the minimum cost is $9$, and there is one permutation $P = (1,2)$ that achieves it.\nFor the second test case, $P = (1,2,3),(2,1,3)$ achieve the minimum cost of $7$.\nFor the third test case, $P = (1,2,3,4),(2,1,3,4),(1,2,4,3),(2,1,4,3)$ achieve the minimum cost of $6$.\nFor the fourth test case, all permutations of $(1,2,3,4,5)$ achieve the minimum cost of $5000000000$."]],"created_at":"2026-03-03 11:01:13"}}