{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eLittle Sub loves playing the game \u003ci\u003eFlip Me Please\u003c/i\u003e. In the game, $n$ lights, numbered from 1 to $n$, are connected separately to $n$ switches. The lights may be either on or off initially, and pressing the $i$-th switch will change the $i$-th light to its opposite status (that is to say, if the $i$-th light is on, it will be off after the $i$-th switch is pressed, and vice versa).\u003c/p\u003e\n\n\u003cp\u003eThe game is composed of exactly $k$ rounds, and in each round, the player must press exactly $m$ different switches. The goal of the game is to change the lights into their target status when the game ends.\u003c/p\u003e\n\n\u003cp\u003eLittle Sub has just come across a very hard challenge and he cannot solve it. As his friend, it\u0027s your responsibility to find out how many solutions there are to solve the challenge and tell him the answer modulo 998244353.\u003c/p\u003e\n\n\u003cp\u003eWe consider two solutions to be different if there exist two integers $i$ and $j$ such that $1 \\le i \\le k$, $1 \\le j \\le n$ and the $j$-th switch is pressed during the $i$-th round of the first solution while it is not pressed during the $i$-th round of the second solution, or vice versa.\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$ (about 1000), indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains three integers $n$, $k$, $m$ ($1 \\leq n,k \\leq 100$, $1 \\leq m \\leq n$).\u003c/p\u003e\n\n\u003cp\u003eThe second line contains a string $s$ ($|s| \u003d n$) consisting of only \u00270\u0027 and \u00271\u0027, indicating the initial status of the lights. If the $i$-th character is \u00271\u0027, the $i$-th light is initially on; If the $i$-th character is \u00270\u0027, the $i$-th light is initially off.\u003c/p\u003e\n\n\u003cp\u003eThe third line contains a string $t$ ($|t| \u003d n$) consisting of only \u00270\u0027 and \u00271\u0027, indicating the target status of the lights. If the $i$-th character is \u00271\u0027, the $i$-th light must be on at the end of the game; If the $i$-th character is \u00270\u0027, the $i$-th light must be off at the end of the game.\u003c/p\u003e\n\n\u003cp\u003eIt is guaranteed that there won\u0027t be more than 100 test cases that $n \u0026gt; 20$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line containing one integer, indicating the answer.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n3 2 1\n001\n100\n3 1 2\n001\n100\n3 3 2\n001\n100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1\n7\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eFor the first sample test case, Little Sub can press the 1st switch in the 1st round and the 3rd switch in the 2nd round; Or he can press the 3rd switch in the 1st round and the 1st switch in the 2nd round. So the answer is 2.\u003c/p\u003e\n\n\u003cp\u003eFor the second sample test case, Little Sub can only press the 1st and the 3rd switch in the 1st and only round. So the answer is 1.\u003c/p\u003e\n"}}]}