{"raw_statement":[{"iden":"problem statement","content":"You are given a permutation $P=(P_1,P_2,\\dots,P_N)$ of $(1,2,\\dots,N)$. You will perform the following operation $M$ times:\n\n*   Choose a pair of integers $(i, j)$ such that $1 \\le i < j \\le N$, and swap $P_i$ and $P_j$.\n\nThere are $\\left(\\frac{N(N-1)}{2}\\right)^M$ possible sequences of operations. For each of them, consider the value $\\sum_{i=1}^{N-1} |P_i - P_{i+1}|$ after all the operations. Find the sum, modulo $998244353$, of all those values."},{"iden":"constraints","content":"*   $2 \\le N \\le 2 \\times 10^5$\n*   $1 \\le M \\le 2 \\times 10^5$\n*   $(P_1,P_2,\\dots,P_N)$ is a permutation of $(1,2,\\dots,N)$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$P_1$ $P_2$ $\\dots$ $P_N$"},{"iden":"sample input 1","content":"3 1\n1 3 2"},{"iden":"sample output 1","content":"8\n\nThere are three possible sequences of operations:\n\n*   Choose $(i,j) = (1,2)$, making $P=(3,1,2)$.\n*   Choose $(i,j) = (1,3)$, making $P=(2,3,1)$.\n*   Choose $(i,j) = (2,3)$, making $P=(1,2,3)$.\n\nThe values of $\\sum_{i=1}^{N-1} |P_i - P_{i+1}|$ for these cases are $3$, $3$, $2$, respectively. Thus, the answer is $3 + 3 + 2 = 8$."},{"iden":"sample input 2","content":"2 5\n2 1"},{"iden":"sample output 2","content":"1"},{"iden":"sample input 3","content":"5 2\n3 5 1 4 2"},{"iden":"sample output 3","content":"833"},{"iden":"sample input 4","content":"20 24\n14 1 20 6 11 3 19 2 7 10 9 18 13 12 17 8 15 5 4 16"},{"iden":"sample output 4","content":"203984325"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}