{"raw_statement":[{"iden":"statement","content":"Insertion sort is a simple sorting algorithm that builds the final sorted array one item at an iteration.\n\nMore precisely, insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.\n\nThis type of sorting is typically done in-place, by iterating up the array, growing the sorted array behind it. At each array-position, it checks the value there against the largest value in the sorted array (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted array, shifts all the larger values up to make a space, and inserts into that correct position.\n\nThe resulting array after $k$ iterations has the property where the first $k$ entries are sorted. In each iteration the first remaining entry of the input is removed, and inserted into the result at the correct position, thus extending the result.\n\nKnuth is an ACM-ICPC master and provides a modified pseudocode implementation about the insertion sort for you. His modified algorithm for an array of sortable items $A$ ($1$-based array) can be expressed as:\n\nHe notes that a permutation of $1$ to $n$ is almost sorted if the length of its longest increasing subsequence is at least $(n -1)$.\n\nGiven the parameter $k$, you are asked to count the number of distinct permutations of $1$ to $n$ meeting the condition that, after his modified insertion sort, each permutation would become an almost sorted permutation.\n\nThe input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $5000$.\n\nFor each test case, the only line contains three integers $n, k$ and $q$ indicating the length of the permutations, the parameter in his implementation and a prime number required for the output respectively, where $1 <= n, k <= 50$ and $10^8 <= q <= 10^9$.\n\nFor each test case, output a line containing \"_Case #x: y_\" (without quotes), where _x_ is the test case number starting from $1$, and _y_ is the remainder of the number of permutations which meet the requirement divided by $q$.\n\nIn the first sample case, we can discover $10$ permutations which meet the condition, and they are listed as follows:\n\n"},{"iden":"input","content":"The input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $5000$.For each test case, the only line contains three integers $n, k$ and $q$ indicating the length of the permutations, the parameter in his implementation and a prime number required for the output respectively, where $1 <= n, k <= 50$ and $10^8 <= q <= 10^9$."},{"iden":"output","content":"For each test case, output a line containing \"_Case #x: y_\" (without quotes), where _x_ is the test case number starting from $1$, and _y_ is the remainder of the number of permutations which meet the requirement divided by $q$."},{"iden":"note","content":"In the first sample case, we can discover $10$ permutations which meet the condition, and they are listed as follows:  $[ 1, 2, 3, 4 ]$;  $[ 1, 2, 4, 3 ]$;  $[ 1, 3, 2, 4 ]$;  $[ 1, 3, 4, 2 ]$;  $[ 1, 4, 2, 3 ]$;  $[ 2, 1, 3, 4 ]$;  $[ 2, 3, 1, 4 ]$;  $[ 2, 3, 4, 1 ]$;  $[ 3, 1, 2, 4 ]$;  $[ 4, 1, 2, 3 ]$. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ C = (c_1, c_2, c_3, c_4, c_5) $ be a sequence of five cards, where each $ c_i = (r_i, s_i) $, with:  \n- $ r_i \\in \\{2, 3, 4, 5, 6, 7, 8, 9, 10, \\text{J}, \\text{Q}, \\text{K}, \\text{A}\\} $: rank of card $ i $,  \n- $ s_i \\in \\{\\text{D}, \\text{H}, \\text{C}, \\text{S}\\} $: suit of card $ i $.  \n\nDefine the score function $ f: \\{2,3,\\dots,10,\\text{J},\\text{Q},\\text{K},\\text{A}\\} \\to \\mathbb{N} $:  \n$$\nf(r) = \n\\begin{cases}\nr & \\text{if } r \\in \\{2,3,\\dots,10\\}, \\\\\n10 & \\text{if } r \\in \\{\\text{J}, \\text{Q}, \\text{K}, \\text{A}\\}.\n\\end{cases}\n$$  \n\nLet $ S_0 = \\sum_{i=1}^5 f(r_i) $: initial hand score.  \n\nDefine the ordered rank sequence $ R = (r_1, r_2, r_3, r_4, r_5) $, and map ranks to numeric values:  \n$$\n\\text{val}(r) = \n\\begin{cases}\n2 & r=2 \\\\\n3 & r=3 \\\\\n\\vdots & \\vdots \\\\\n10 & r=10 \\\\\n11 & r=\\text{J} \\\\\n12 & r=\\text{Q} \\\\\n13 & r=\\text{K} \\\\\n14 & r=\\text{A}\n\\end{cases}\n$$\n\nLet $ V = (\\text{val}(r_1), \\text{val}(r_2), \\text{val}(r_3), \\text{val}(r_4), \\text{val}(r_5)) $, sorted as $ V_{\\text{sorted}} $.  \n\nDefine a *straight* as a sequence of five consecutive integers in $ V_{\\text{sorted}} $, i.e., $ V_{\\text{sorted}} = (x, x+1, x+2, x+3, x+4) $ for some $ x \\in \\{2,3,\\dots,10\\} $.  \n\nDefine *flush* as $ s_1 = s_2 = s_3 = s_4 = s_5 $.  \n\nDefine *all same rank* as $ r_1 = r_2 = r_3 = r_4 = r_5 $.  \n\n**Constraints**  \nAll cards are valid; input has exactly five cards.  \n\n**Rules (applied in order, each modifies current score $ S $):**  \n1. If all five cards have the same rank, set $ S \\leftarrow S + 100 $.  \n2. If the hand is a flush, set $ S \\leftarrow S + 50 $.  \n3. If the hand is a straight, set $ S \\leftarrow S + 25 $.  \n4. If there are exactly four cards of the same rank, set $ S \\leftarrow S + 20 $.  \n5. If there are exactly three cards of the same rank and two of another rank (full house), set $ S \\leftarrow S + 15 $.  \n6. If there are exactly three cards of the same rank, set $ S \\leftarrow S + 10 $.  \n7. If there are exactly two pairs of cards with same rank, set $ S \\leftarrow S + 5 $.  \n8. If there is exactly one pair of cards with same rank, set $ S \\leftarrow S + 2 $.  \n9. If the hand contains a 2 and a 3 and a 4 and a 5 and a 6, set $ S \\leftarrow S + 1 $.  \n10. If the hand contains a 7 and a 8 and a 9 and a 10 and a J, set $ S \\leftarrow S + 1 $.  \n11. If the hand contains a 8 and a 9 and a 10 and a J and a Q, set $ S \\leftarrow S + 1 $.  \n12. If the hand contains a 9 and a 10 and a J and a Q and a K, set $ S \\leftarrow S + 1 $.  \n13. If the hand contains a 10 and a J and a Q and a K and an A, set $ S \\leftarrow S + 1 $.  \n14. If the hand contains an A and a 2 and a 3 and a 4 and a 5, set $ S \\leftarrow S + 1 $.  \n\n**Objective**  \nCompute the final score $ S $ after applying rules 1 through 14 in order, starting from $ S_0 $.","simple_statement":"You are given 5 cards. Each card has a rank (2-10, J, Q, K, A) and a suit (D, H, C, S).  \nScore each card: 2–10 = face value, J/Q/K/A = 10.  \nStart with the sum of all 5 card scores.  \nThen apply 14 rules in order (rules not listed, but you must apply all 14).  \nOutput the final score.","has_page_source":false}