{"trustable":false,"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":"MD","content":"阅读以下插入排序的伪代码。\n\n```\nfunction InsertionsSort(A, k)\t // Elements in A would be modified\n\tn ← the length of A\n\ti ← 1\n\twhile i ≤ n and i ≤ k do\t\t\t\t\t// the i-th iteration\n\t\tj ← i\n\t\twhile j \u003e 1 and A[j-1] \u003e A[j] do\n\t\t\tt ← A[j]\n\t\t\tA[j] ← A[j-1]\n\t\t\tA[j-1] ← t\n\t\t\tj ← j-1\n\t\tend while\n\t\ti ← i+1\n\tend while\nend function\n```\n\n我们定义一个长度为 `n` 的排列是几乎排好序的,当且仅当它的最长上升子序列长度至少为 `n-1`。\n\n给定参数 `k`,你现在需要数出有多少组不同的1-n的排列,满足在运行过上述插入排序算法之后,它变成一个几乎排好序的排列。"}},{"title":"输入","value":{"format":"MD","content":"输入包含多组测试样例,第一行包含数字 `T` 表示用例数,并且不超过5000。\n\n对于每组测试样例,一行数字 `n, k, q` 分别表示排列的长度,上述代码中的参数和一个素数。其中 1 ≤ n, k ≤ 50, 10\u003csup\u003e8\u003c/sup\u003e ≤ q ≤ 10\u003csup\u003e9\u003c/sup\u003e。"}},{"title":"输出","value":{"format":"MD","content":"对于每组样例,输出一行包含 `Case #x: y`,其中 `x` 是以1开始的编号,`y` 是符合要求的排列对 `q` 取模的余数。"}},{"title":"样例输入","value":{"format":"MD","content":"```\n4\n4 1 998244353\n4 2 998244353\n4 3 998244353\n4 4 998244353\n```"}},{"title":"样例输出","value":{"format":"MD","content":"```\nCase #1: 10\nCase #2: 14\nCase #3: 24\nCase #4: 24\n```"}},{"title":"提示","value":{"format":"MD","content":"对于第一组测试样例,我们找到了 10 组排列满足条件,它们分别是:\n\n- [1, 2, 3, 4]\n- [1, 2, 4, 3]\n- [1, 3, 2, 4]\n- [1, 3, 4, 2]\n- [1, 4, 2, 3]\n- [2, 1, 3, 4]\n- [2, 3, 1, 4]\n- [2, 3, 4, 1]\n- [3, 1, 2, 4]\n- [4, 1, 2, 3]"}}]}