{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eWe start with a permutation $$$a_1, a_2, \\ldots, a_n$$$ and with an empty array $$$b$$$. We apply the following operation $$$k$$$ times.\u003c/p\u003e\u003cp\u003eOn the $$$i$$$-th iteration, we select an index $$$t_i$$$ ($$$1 \\le t_i \\le n-i+1$$$), remove $$$a_{t_i}$$$ from the array, and append one of the numbers $$$a_{t_i-1}$$$ or $$$a_{t_i+1}$$$ (if $$$t_i-1$$$ or $$$t_i+1$$$ are within the array bounds) to the right end of the array $$$b$$$. Then we move elements $$$a_{t_i+1}, \\ldots, a_n$$$ to the left in order to fill in the empty space.\u003c/p\u003e\u003cp\u003eYou are given the initial permutation $$$a_1, a_2, \\ldots, a_n$$$ and the resulting array $$$b_1, b_2, \\ldots, b_k$$$. All elements of an array $$$b$$$ are \u003cspan class\u003d\"tex-font-style-bf\"\u003edistinct\u003c/span\u003e. Calculate the number of possible sequences of indices $$$t_1, t_2, \\ldots, t_k$$$ modulo $$$998\\,244\\,353$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eEach test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \\le t \\le 100\\,000$$$), denoting the number of test cases, followed by a description of the test cases.\u003c/p\u003e\u003cp\u003eThe first line of each test case contains two integers $$$n, k$$$ ($$$1 \\le k \u0026lt; n \\le 200\\,000$$$): sizes of arrays $$$a$$$ and $$$b$$$.\u003c/p\u003e\u003cp\u003eThe second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \\ldots, a_n$$$ ($$$1 \\le a_i \\le n$$$): elements of $$$a$$$. All elements of $$$a$$$ are \u003cspan class\u003d\"tex-font-style-bf\"\u003edistinct\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eThe third line of each test case contains $$$k$$$ integers $$$b_1, b_2, \\ldots, b_k$$$ ($$$1 \\le b_i \\le n$$$): elements of $$$b$$$. All elements of $$$b$$$ are \u003cspan class\u003d\"tex-font-style-bf\"\u003edistinct\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eThe sum of all $$$n$$$ among all test cases is guaranteed to not exceed $$$200\\,000$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case print one integer: the number of possible sequences modulo $$$998\\,244\\,353$$$.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\n5 3\n1 2 3 4 5\n3 2 5\n4 3\n4 3 2 1\n4 3 1\n7 4\n1 4 7 3 6 2 5\n3 2 4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n0\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003e$$$\\require{cancel}$$$\u003c/p\u003e\u003cp\u003eLet\u0027s denote as $$$a_1 a_2 \\ldots \\cancel{a_i} \\underline{a_{i+1}} \\ldots a_n \\rightarrow a_1 a_2 \\ldots a_{i-1} a_{i+1} \\ldots a_{n-1}$$$ an operation over an element with index $$$i$$$: removal of element $$$a_i$$$ from array $$$a$$$ and appending element $$$a_{i+1}$$$ to array $$$b$$$.\u003c/p\u003e\u003cp\u003eIn the first example test, the following two options can be used to produce the given array $$$b$$$:\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$1 2 \\underline{3} \\cancel{4} 5 \\rightarrow 1 \\underline{2} \\cancel{3} 5 \\rightarrow 1 \\cancel{2} \\underline{5} \\rightarrow 1 2$$$; $$$(t_1, t_2, t_3) \u003d (4, 3, 2)$$$; \u003c/li\u003e\u003cli\u003e $$$1 2 \\underline{3} \\cancel{4} 5 \\rightarrow \\cancel{1} \\underline{2} 3 5 \\rightarrow 2 \\cancel{3} \\underline{5} \\rightarrow 1 5$$$; $$$(t_1, t_2, t_3) \u003d (4, 1, 2)$$$. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eIn the second example test, it is impossible to achieve the given array no matter the operations used. That\u0027s because, on the first application, we removed the element next to $$$4$$$, namely number $$$3$$$, which means that it couldn\u0027t be added to array $$$b$$$ on the second step.\u003c/p\u003e\u003cp\u003eIn the third example test, there are four options to achieve the given array $$$b$$$:\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$1 4 \\cancel{7} \\underline{3} 6 2 5 \\rightarrow 1 4 3 \\cancel{6} \\underline{2} 5 \\rightarrow \\cancel{1} \\underline{4} 3 2 5 \\rightarrow 4 3 \\cancel{2} \\underline{5} \\rightarrow 4 3 5$$$;\u003c/li\u003e\u003cli\u003e $$$1 4 \\cancel{7} \\underline{3} 6 2 5 \\rightarrow 1 4 3 \\cancel{6} \\underline{2} 5 \\rightarrow 1 \\underline{4} \\cancel{3} 2 5 \\rightarrow 1 4 \\cancel{2} \\underline{5} \\rightarrow 1 4 5$$$;\u003c/li\u003e\u003cli\u003e $$$1 4 7 \\underline{3} \\cancel{6} 2 5 \\rightarrow 1 4 7 \\cancel{3} \\underline{2} 5 \\rightarrow \\cancel{1} \\underline{4} 7 2 5 \\rightarrow 4 7 \\cancel{2} \\underline{5} \\rightarrow 4 7 5$$$;\u003c/li\u003e\u003cli\u003e $$$1 4 7 \\underline{3} \\cancel{6} 2 5 \\rightarrow 1 4 7 \\cancel{3} \\underline{2} 5 \\rightarrow 1 \\underline{4} \\cancel{7} 2 5 \\rightarrow 1 4 \\cancel{2} \\underline{5} \\rightarrow 1 4 5$$$;\u003c/li\u003e\u003c/ul\u003e"}}]}