{"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\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.\u003c/p\u003e\u003cp\u003eIzdihar is an ACM-ICPC master and provides a pseudocode implementation about the bubble sort for you. The algorithm for a list of sortable items A can be expressed as (1-based array):\u003c/p\u003e\u003col\u003e \u003cli\u003e n \u003d length(A) \u003c/li\u003e\u003cli\u003e repeat \u003col\u003e \u003cli\u003e swapped \u003d false \u003c/li\u003e\u003cli\u003e for i \u003d 2 to n inclusive do \u003col\u003e \u003cli\u003e if A[i-1] \u0026gt; A[i] then \u003col\u003e \u003cli\u003e swap( A[i-1], A[i] ) \u003c/li\u003e\u003cli\u003e swapped \u003d true \u003c/li\u003e\u003c/ol\u003e end if \u003c/li\u003e\u003c/ol\u003e end for \u003c/li\u003e\u003c/ol\u003e until not swapped \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eShe says a permutation of $$$1$$$ to $$$n$$$ is almost sorted if the length of its longest increasing subsequence is at least $$$n-1$$$.\u003c/p\u003e\u003cp\u003eYou are asked to count the number of permutations of $$$1$$$ to $$$n$$$ which, after $$$k$$$ times passing through the list in the bubble sort, would become an almost sorted permutation.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input contains several test cases, and the first line is a positive $$$T$$$ indicating the number of test cases which is up to $$$5000$$$.\u003c/p\u003e\u003cp\u003eFor each test case, a line contains three integers $$$n$$$, $$$k~(1 \\leq n, k \\leq 50)$$$ which are described as above, and $$$q~(10^8 \\leq q \\leq 10^9)$$$ which is a prime number for the output.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output a line containing \u003cspan class\u003d\"tex-font-style-tt\"\u003eCase #x: y\u003c/span\u003e, where \u003cspan class\u003d\"tex-font-style-tt\"\u003ex\u003c/span\u003e is the test case number starting from $$$1$$$. And \u003cspan class\u003d\"tex-font-style-tt\"\u003ey\u003c/span\u003e is the remainder of the number of permutations which meet the requirement, dividing by $$$q$$$.\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\u003e5\n5 1 998244353\n5 2 998244353\n5 3 998244353\n5 4 998244353\n5 5 998244353\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 74\nCase #2: 114\nCase #3: 120\nCase #4: 120\nCase #5: 120\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}