{"raw_statement":[{"iden":"statement","content":"_If you want to practice topicwise questions in the ladder way like a2oj , do register on my site *http://codedigger.tech* after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck._\n\nSinghal has a string $S$ consisting of lowercase English letters. He wants to form lexicographical smallest string by applying a operation atmost once.\n\nOperation is —\n\nChoose three distinct indices $i_1, i_2, i_3$ such that $1 <= i_i < i_2 < i_3 <= | S |$, where $| S |$ is the length of string and perform cyclic right shift on these indices.\n\nIf value at $i_1, i_2, i_3$ is $s_1, s_2, s_3$, then after performing right cyclic shift on these indices, value at indices will change to $i_2 arrow.r s_1, i_3 arrow.r s_2, i_1 arrow.r s_3$.\n\nExample - $S =$ \"codedigger\". Chosen indices is $1, 2, 3$ then resultant string will be $S =$ \"dcoedigger\".\n\nA string a is lexicographical smaller than a string b if and only if one of the following holds:\n\nThe first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.\n\nEach query contains a string $S (1 <= | S | <= 10^5)$ consisting of lowercase English letters. $| S |$ is the length of the string.\n\nIt is guaranteed that the total sum of $| S |$ is at most $10^5$.\n\nPrint $t$ answers to the test cases. Each answer must be consisting of single lexicographical smallest possible string.\n\nIn the first query, apply right cyclic shift on indices $1, 2, 3$ to get the smallest possible string $S =$ _aab_.\n\nIn the second or third query , if we apply operation we get lexicographical larger string. So we will not apply any operation.\n\n"},{"iden":"input","content":"The first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.Each query contains a string $S (1 <= | S | <= 10^5)$ consisting of lowercase English letters. $| S |$ is the length of the string.It is guaranteed that the total sum of $| S |$ is at most $10^5$."},{"iden":"output","content":"Print $t$ answers to the test cases. Each answer must be consisting of single lexicographical smallest possible string."},{"iden":"note","content":"In the first query, apply right cyclic shift on indices $1, 2, 3$ to get the smallest possible string $S =$ _aab_.In the second or third query , if we apply operation we get lexicographical larger string. So we will not apply any operation."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of sequences.  \nLet $ S_n $ be the set of all $ n $-holy sequences (defined as all sequences of length $ n $ with elements in $ \\{1, 2, \\dots, n\\} $).  \nFor a sequence $ p \\in S_n $ and $ t \\in \\{1, 2, \\dots, n\\} $, let $ \\mathrm{cnt}(p, t) $ denote the number of occurrences of $ t $ in $ p $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 3000 $  \n2. $ 1 \\leq m \\leq 10^9 $  \n3. Total sum of $ n $ across test cases $ \\leq 10^4 $  \n\n**Objective**  \nFor each $ t \\in \\{1, 2, \\dots, n\\} $, compute:  \n$$\n\\sum_{p \\in S_n} \\mathrm{cnt}(p, t)^2 \\mod m\n$$  \nOutput the result for each $ t = 1 $ to $ n $.","simple_statement":"Alex defines a sequence as \"n-holy\" if it contains exactly the numbers 1 through n, each exactly once.\n\nFor each t from 1 to n, compute the sum of (count of t in p)² over all n-holy sequences p, modulo m.\n\nSince each sequence is a permutation of 1 to n, every number t appears exactly once in each sequence.\n\nSo (count of t in p)² = 1² = 1 for every sequence p.\n\nThere are n! total sequences.\n\nAnswer for each t is n! mod m.\n\nOutput n copies of (n! mod m), one for each t from 1 to n.","has_page_source":false}