{"raw_statement":[{"iden":"problem statement","content":"In the Kingdom of Takahashi, $N$ citizens numbered $1$ to $N$ took an examination of competitive programming.  \nThere were two tests, and Citizen $i$ ranked $P_i$\\-th in the first test and $Q_i$\\-th in the second test.  \nThere were no ties in either test. That is, each of the sequences $P$ and $Q$ is a permutation of $(1, 2, ..., N)$.\nIroha, the president of the kingdom, is going to select $K$ citizens for the national team at the coming world championship of competitive programming.  \nThe members of the national team must be selected so that the following is satisfied.\n\n*   There should not be a pair of citizens $(x, y)$ where Citizen $x$ is selected and Citizen $y$ is not selected such that $P_x > P_y$ and $Q_x > Q_y$.\n    *   In other words, if Citizen $y$ got a rank smaller than that of Citizen $x$ in both tests, it is not allowed to select Citizen $x$ while not selecting Citizen $y$.\n\nTo begin with, Iroha wants to know the number of ways to select citizens for the national team that satisfy the condition above. Find it to help her.  \nSince this number can be enormous, print it modulo $998244353$."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\le N \\le 300$\n*   $1 \\le K \\le N$\n*   Each of $P$ and $Q$ is a permutation of $(1,2,...,N)$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$\n$P_1$ $P_2$ $\\dots$ $P_N$\n$Q_1$ $Q_2$ $\\dots$ $Q_N$"},{"iden":"sample input 1","content":"4 2\n2 4 3 1\n2 1 4 3"},{"iden":"sample output 1","content":"3\n\n*   It is fine to select Citizen $1$ and Citizen $2$ for the team.\n*   If Citizen $1$ and Citizen $3$ are selected, Citizen $4$ ranked higher than Citizen $3$ did in both tests, so the pair $(x,y)=(3,4)$ would violate the condition in the Problem Statement.\n*   It is fine to select Citizen $1$ and Citizen $4$.\n*   If Citizen $2$ and Citizen $3$ are selected, the pair $(x,y)=(3,1)$ would violate the condition.\n*   It is fine to select Citizen $2$ and Citizen $4$.\n*   If Citizen $3$ and Citizen $4$ are selected, the pair $(x,y)=(3,1)$ would violate the condition.\n\nThe final answer is $3$."},{"iden":"sample input 2","content":"33 16\n1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33\n33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1"},{"iden":"sample output 2","content":"168558757\n\nAll $\\binom{33}{16} = 1166803110$ ways of selecting $16$ from the $33$ citizens satisfy the requirement.  \nTherefore, we should print $1166803110$ modulo $998244353$, that is, $168558757$."},{"iden":"sample input 3","content":"15 7\n4 9 7 5 6 13 2 11 3 1 12 14 15 10 8\n4 14 9 12 7 15 1 2 8 11 3 5 13 6 10"},{"iden":"sample output 3","content":"23"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}