{"problem":{"name":"Random Student ID","description":{"content":"Takahashi Elementary School has $N$ new students. For $i = 1, 2, \\ldots, N$, the name of the $i$\\-th new student is $S_i$ (which is a string consisting of lowercase English letters). The names of the ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc268_g"},"statements":[{"statement_type":"Markdown","content":"Takahashi Elementary School has $N$ new students. For $i = 1, 2, \\ldots, N$, the name of the $i$\\-th new student is $S_i$ (which is a string consisting of lowercase English letters). The names of the $N$ new students are distinct.\nThe $N$ students will be assigned a student ID $1, 2, 3, \\ldots, N$ in **ascending lexicographical order** of their names. However, instead of the ordinary order of lowercase English letters where `a` is the minimum and `z` is the maximum, we use the following order:\n\n*   First, Principal Takahashi chooses a string $P$ from the $26!$ permutations of the string `abcdefghijklmnopqrstuvwxyz` of length $26$, uniformly at random.\n*   The lowercase English characters that occur earlier in $P$ are considered smaller.\n\nFor each of the $N$ students, find the expected value, modulo $998244353$, of the student ID assigned (see Notes).\nWhat is the lexicographical order?A string $S = S_1S_2\\ldots S_{|S|}$ is said to be **lexicographically smaller** than a string $T = T_1T_2\\ldots T_{|T|}$ if one of the following 1. and 2. holds. Here, $|S|$ and $|T|$ denote the lengths of $S$ and $T$, respectively.\n\n1.  $|S| \\lt |T|$ and $S_1S_2\\ldots S_{|S|} = T_1T_2\\ldots T_{|S|}$.\n2.  There exists an integer $1 \\leq i \\leq \\min\\lbrace |S|, |T| \\rbrace$ satisfying the following two conditions:\n    *   $S_1S_2\\ldots S_{i-1} = T_1T_2\\ldots T_{i-1}$\n    *   $S_i$ is a smaller character than $T_i$.\n\n## Constraints\n\n*   $2 \\leq N$\n*   $N$ is an integer.\n*   $S_i$ is a string of length at least $1$ consisting of lowercase English letters.\n*   The sum of lengths of the given strings is at most $5 \\times 10^5$.\n*   $i \\neq j \\Rightarrow S_i \\neq S_j$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$\n\n[samples]\n\n## Notes\n\nWe can prove that the sought expected value is always a rational number. Moreover, under the Constraints of this problem, when the value is represented as $\\frac{P}{Q}$ by two coprime integers $P$ and $Q$, we can prove that there is a unique integer $R$ such that $R \\times Q \\equiv P\\pmod{998244353}$ and $0 \\leq R \\lt 998244353$. Find such $R$.","is_translate":false,"language":"English"}],"meta":{"iden":"abc268_g","tags":[],"sample_group":[["3\na\naa\nab","1\n499122179\n499122179\n\nThe expected value of the student ID assigned to Student $1$ is $1$; the expected values of the student ID assigned to Student $2$ and $3$ are $\\frac{5}{2}$.\nNote that the answer should be printed modulo $998244353$. For example, the sought expected value for Student $2$ and $3$ is $\\frac{5}{2}$, and we have $2 \\times 499122179 \\equiv 5\\pmod{998244353}$, so $499122179$ should be printed."],["3\na\naa\naaa","1\n2\n3"]],"created_at":"2026-03-03 11:01:14"}}