{"raw_statement":[{"iden":"statement","content":"Andi is getting married! He and his partner plan to have $N$ children. To avoid any hassle in the future, Andi wants to decide all their children's name in advance. Specifically, he wants each child to have a name which is lexicographically *larger* than any of his/her older siblings. Of course, his partner also agrees with this idea. String $A$ is lexicographically larger than string $B$ if and only if $B$ is a prefix of $A$ or there exists an index $i$ where $A_i > B_i$ and $A_j = B_j$ for all $j < i$. Note that a proper name can be as short as one character, but it *cannot* be an empty string.\n\nLife is good for Andi, until one day he told his soon-to-be-grandmother-in-law (i.e. his partner's grandma) about this marriage plan. After learning that Andi plans to have $N$ children with her granddaughter, she gave him $N$ names to be used. Moreover, the $i^(t h)$ name can only be used for the $i^(t h)$ child.\n\nAfter going through a long debate with her grandma, Andi came into an agreement: The $i^(t h)$ child's name should be a subsequence of the $i^(t h)$ name her grandma gave. A string $A$ is a subsequence of string $B$ if $A$ can be obtained by deleting zero or more characters from $B$ without changing the remaining characters' order, e.g., _ABC_ is a subsequence of _DAEBCCB_, but _EFG_ is not a subsequence of _FABEGC_.\n\nEven though Andi dislikes the given list of names, he still wants to impress his partner by showing that he can satisfy both her grandma's wish and his own desire (i.e. each child's name is lexicographically larger than any of his/her older siblings). However, Andi wonders, what is the maximum possible total length of their children names?\n\nFor example, let $N = 3$, and the names given by his partner's grandma are $($_KARIM_$,$ _PARBUDI_$,$ _CHANDRA_$)$. Here are several example set of names which satisfies Andi's desire: \n\nInput begins with a line containing an integer $N$ ($1 <= N <= 15$) representing the number of children. The next $N$ lines, each contains a string $S_i$ ($1 <= | S_i | <= 15$) representing the $i^(t h)$ name given by Andi's soon-to-be-grandmother-in-law. $S_i$ contains only uppercase alphabets ($S_{i j} in {A -Z}$).\n\nOutput contains an integer in a line representing the maximum possible total length of their children names, or _-1_ if no possible valid set of names can be obtained.\n\n_Explanation for the sample input/output #3_\n\nOne possible solution is $[ texttt(A V E), texttt(F U N), texttt(I N), texttt(I P C), texttt(J A K A R T A), texttt(N T Y), texttt(T E E N) ]$ with a total length of $3 + 3 + 2 + 3 + 7 + 3 + 4 = 25$.\n\n"},{"iden":"input","content":"Input begins with a line containing an integer $N$ ($1 <= N <= 15$) representing the number of children. The next $N$ lines, each contains a string $S_i$ ($1 <= | S_i | <= 15$) representing the $i^(t h)$ name given by Andi's soon-to-be-grandmother-in-law. $S_i$ contains only uppercase alphabets ($S_{i j} in {A -Z}$)."},{"iden":"output","content":"Output contains an integer in a line representing the maximum possible total length of their children names, or _-1_ if no possible valid set of names can be obtained."},{"iden":"examples","content":"Input3\nKARIM\nPARBUDI\nCHANDRA\nOutput16\nInput2\nZORO\nANDI\nOutput-1\nInput7\nHAVE\nFUN\nIN\nICPC\nJAKARTA\nTWENTY\nEIGHTEEN\nOutput25\n"},{"iden":"note","content":"_Explanation for the sample input/output #3_One possible solution is $[ texttt(A V E), texttt(F U N), texttt(I N), texttt(I P C), texttt(J A K A R T A), texttt(N T Y), texttt(T E E N) ]$ with a total length of $3 + 3 + 2 + 3 + 7 + 3 + 4 = 25$."}],"translated_statement":[{"iden":"statement","content":"Monocarp 将参加 $n$ 场不同的编程竞赛，并计划在每场竞赛中赢得一件 T 恤。当然，他不需要 $n$ 件 T 恤——他想把它们全部送给朋友。Monocarp 有一个包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$ 的列表——表示他的朋友们希望收到的 T 恤尺寸。所有 $a_i$ 的值互不相同。\n\n为了给所有 $n$ 位朋友都拿到 T 恤，Monocarp 在注册不同比赛时选择不同的 T 恤尺寸：在注册第 $i$ 场比赛时，他指定希望收到尺寸为 $a_i$ 的 T 恤。\n\nMonocarp 相信自己的编程能力足以在每场竞赛中赢得 T 恤。但不幸的是，他可能收到尺寸错误的 T 恤：如果他指定想要尺寸为 $x$ 的 T 恤，则以概率 $p$ 收到尺寸为 $x -1$ 的 T 恤，以概率 $q$ 收到尺寸为 $x + 1$ 的 T 恤，以概率 $1 -p -q$ 收到尺寸为 $x$ 的 T 恤。\n\n在收到所有 T 恤后，Monocarp 开始分发：对于每个 $a_i$，如果他至少收到一件尺寸为 $a_i$ 的 T 恤，他就将恰好一件该尺寸的 T 恤送给提出该尺寸需求的朋友。现在 Monocarp 想知道平均有多少位朋友能收到 T 恤。请帮助他计算他将送出的 T 恤数量的期望值。\n\n第一行包含三个整数 $n$, $P$ 和 $Q$（$1 lt.eq n lt.eq 2 dot.op 10^5$, $0 lt.eq P lt.eq 10^6$, $0 lt.eq Q lt.eq 10^6$, $P + Q lt.eq 10^6$）——分别表示比赛场数和表示收到错误尺寸 T 恤概率的数值。题目中的 $p$ 和 $q$ 可通过以下方式计算：$p = frac(P, 10^6)$，$q = frac(Q, 10^6)$。\n\n第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$（$1 lt.eq a_i lt.eq 10^9$）——表示 Monocarp 的朋友们希望收到的 T 恤尺寸。所有 $a_i$ 的值互不相同。\n\nMonocarp 将送出的 T 恤数量的期望值可以表示为一个最简分数 $frac(X, Y)$，其中 $Y$ 不被 $998244353$ 整除。请输出 $(X dot.op Y^(-1))$ $m o d$ $998244353$，其中 $Y^(-1)$ 是 $Y$ 在模 $998244353$ 意义下的逆元（即满足 $Y dot.op Y^(-1) \\equiv 1 \\pmod{998244353}$ 的数）。\n\n示例解释：\n\n在第一个示例中，$p = frac(1, 4)$，$q = frac(1, 4)$，答案为 $frac(79, 32)$。\n\n在第二个示例中，$p = frac(1, 8)$，$q = frac(3, 4)$，答案为 $frac(467, 256)$。\n\n"},{"iden":"input","content":"第一行包含三个整数 $n$, $P$ 和 $Q$（$1 lt.eq n lt.eq 2 dot.op 10^5$, $0 lt.eq P lt.eq 10^6$, $0 lt.eq Q lt.eq 10^6$, $P + Q lt.eq 10^6$）——分别表示比赛场数和表示收到错误尺寸 T 恤概率的数值。题目中的 $p$ 和 $q$ 可通过以下方式计算：$p = frac(P, 10^6)$，$q = frac(Q, 10^6)$。第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$（$1 lt.eq a_i lt.eq 10^9$）——表示 Monocarp 的朋友们希望收到的 T 恤尺寸。所有 $a_i$ 的值互不相同。"},{"iden":"output","content":"Monocarp 将送出的 T 恤数量的期望值可以表示为一个最简分数 $frac(X, Y)$，其中 $Y$ 不被 $998244353$ 整除。请输出 $(X dot.op Y^(-1))$ $m o d$ $998244353$，其中 $Y^(-1)$ 是 $Y$ 在模 $998244353$ 意义下的逆元（即满足 $Y dot.op Y^(-1) \\equiv 1 \\pmod{998244353}$ 的数）。"},{"iden":"examples","content":"输入\n4 250000 250000\n3 1 5 2\n输出\n530317315\n\n输入\n3 125000 750000\n3 2 1\n输出\n175472642\n"},{"iden":"note","content":"示例解释：在第一个示例中，$p = frac(1, 4)$，$q = frac(1, 4)$，答案为 $frac(79, 32)$。在第二个示例中，$p = frac(1, 8)$，$q = frac(3, 4)$，答案为 $frac(467, 256)$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of contests and friends.  \nLet $ a_1, a_2, \\dots, a_n \\in \\mathbb{Z}^+ $ be distinct target T-shirt sizes requested by friends.  \nLet $ p = \\frac{P}{10^6} $, $ q = \\frac{Q}{10^6} $, with $ P, Q \\in \\mathbb{Z} $, $ 0 \\leq P + Q \\leq 10^6 $, and $ r = 1 - p - q $.  \n\nFor each contest $ i \\in \\{1, \\dots, n\\} $, Monocarp registers for size $ a_i $. The received T-shirt size $ X_i $ is a random variable:  \n$$\nX_i = \n\\begin{cases}\na_i - 1 & \\text{with probability } p, \\\\\na_i     & \\text{with probability } r, \\\\\na_i + 1 & \\text{with probability } q.\n\\end{cases}\n$$\n\nLet $ S = \\{X_1, X_2, \\dots, X_n\\} $ be the multiset of received T-shirt sizes.  \nLet $ I_j $ be the indicator random variable for friend $ j $ receiving a T-shirt of size $ a_j $:  \n$$\nI_j = \\mathbb{1}_{\\{a_j \\in S\\}}.\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $  \n2. $ 1 \\leq a_i \\leq 10^9 $, all $ a_i $ distinct  \n3. $ 0 \\leq P, Q \\leq 10^6 $, $ P + Q \\leq 10^6 $  \n\n**Objective**  \nCompute the expected number of friends who receive a T-shirt:  \n$$\n\\mathbb{E}\\left[\\sum_{j=1}^n I_j\\right] = \\sum_{j=1}^n \\mathbb{P}(a_j \\in S)\n$$\n\nFor each $ j $, define:  \n- $ L_j = \\mathbb{P}(\\text{size } a_j \\text{ is received from contest } j-1) = \\mathbb{P}(X_{j-1} = a_j) $ if $ j > 1 $, else 0  \n- $ R_j = \\mathbb{P}(\\text{size } a_j \\text{ is received from contest } j+1) = \\mathbb{P}(X_{j+1} = a_j) $ if $ j < n $, else 0  \n- $ C_j = \\mathbb{P}(\\text{size } a_j \\text{ is received from contest } j) = r $\n\nThen:  \n$$\n\\mathbb{P}(a_j \\in S) = 1 - \\mathbb{P}(\\text{no contest produces } a_j) = 1 - (1 - L_j)(1 - C_j)(1 - R_j)\n$$\n\nThus, the expected number is:  \n$$\n\\sum_{j=1}^n \\left(1 - (1 - L_j)(1 - C_j)(1 - R_j)\\right)\n$$\n\nWhere:  \n- $ C_j = r $ for all $ j $  \n- $ L_j = \\begin{cases} q & \\text{if } a_j = a_{j-1} + 1 \\\\ 0 & \\text{otherwise} \\end{cases} $  \n- $ R_j = \\begin{cases} p & \\text{if } a_j = a_{j+1} - 1 \\\\ 0 & \\text{otherwise} \\end{cases} $\n\nCompute the result modulo $ 998244353 $ as $ \\left( X \\cdot Y^{-1} \\right) \\mod 998244353 $, where $ \\frac{X}{Y} $ is the irreducible form of the expectation.","simple_statement":null,"has_page_source":false}