{"trustable":true,"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":"HTML","content":"\u003cp\u003e给定一个字符串 $$$S$$$,$$$n$$$ 个长度为 $$$m$$$ 的字符串 $$$T_1,T_2,\\dots,T_n$$$,以及一个长度为 $$$k$$$ 的正有理数序列 $$$p$$$,其总和为 $$$1$$$。每个字符串只包含前 $$$k$$$ 个小写字母。让我们执行以下过程:\u003c/p\u003e\u003col\u003e \u003cli\u003e 如果存在 $$$j$$$ $$$(1\\leq j\\leq n)$$$,使得 $$$T_j$$$ 是 $$$S$$$ 的子串,则停止过程。 \u003c/li\u003e\u003cli\u003e 以概率 $$$p_i$$$ 将第 $$$i$$$ 个小写字母附加到 $$$S$$$ 的末尾,然后返回到步骤 1。 \u003c/li\u003e\u003c/ol\u003e 我们定义 $$$f(S;T,p)$$$ 为过程停止时 $$$S$$$ 的期望长度。\u003cp\u003e只计算一个字符串 $$$S$$$ 的 $$$f(S;T,p)$$$ 是很无聊的。为了使问题更加困难,给定了一个字符串 $$$R$$$。让我们将长度为 $$$i$$$ 的 $$$R$$$ 的前缀表示为 $$$R[1\\dots i]$$$。你的任务是计算 $$$i\u003d1,2,\\cdots,|R|$$$ 的 $$$f(R[1\\dots i];T,p)$$$。\u003c/p\u003e\u003cp\u003e可以证明 $$$f(S;T,p)$$$ 是一个正有理数,可以表示为 $$$\\frac PQ$$$,其中 $$$\\gcd(P,Q)\u003d1$$$。保证对于给定输入中的所有字符串 $$$S$$$,在给定 $$$T$$$ 和 $$$p$$$ 的情况下,都有 $$$Q\\not\\equiv 0\\pmod{(10^9+7)}$$$。你应该输出 $$$PQ^{-1}\\mod (10^9+7)$$$ 的值。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含三个正整数 $$$n,m$$$ 和 $$$k$$$($$$1\\leq n\\leq 100$$$,$$$n\\times m\\leq 10\\,000$$$,$$$1\\leq k\\leq 26$$$)。\u003c/p\u003e\u003cp\u003e第二行包含 $$$k$$$ 个正整数 $$$p\u0027_1,p\u0027_2\\cdots,p\u0027_k$$$。保证 $$$p\u0027_1+p\u0027_2+\\cdots+p\u0027_k\u003d100$$$,并且概率 $$$p_i$$$ 等于 $$$\\frac{p\u0027_i}{100}$$$。\u003c/p\u003e\u003cp\u003e接下来的 $$$n$$$ 行中,第 $$$i$$$ 行包含长度为 $$$m$$$ 的字符串 $$$T_i$$$。\u003c/p\u003e\u003cp\u003e最后一行包含一个字符串 $$$R$$$($$$1\\leq|R|\\leq 10\\,000$$$)。\u003c/p\u003e\u003cp\u003e保证每个字符串只包含前 $$$k$$$ 个小写字母,并且在给定输入中,对于所有字符串 $$$S$$$,都有 $$$Q\\not\\equiv 0\\pmod{(10^9+7)}$$$ 表示为 $$$\\frac PQ$$$ 与 $$$\\gcd(P,Q)\u003d1$$$。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出 $$$|R|$$$ 行。第 $$$i$$$ 行包含一个整数,表示 $$$f(R[1\\dots i];T,p)$$$ 的值。\u003c/p\u003e"}},{"title":"样例 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 2 2\n50 50\naa\nbb\nababaa\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n4\n5\n6\n7\n6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"样例 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3 3\n25 25 50\nabc\nbac\ncab\nababbabbcaaa\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e13\n333333343\n333333344\n333333345\n17\n333333347\n333333348\n20\n333333358\n666666692\n23\n24\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"样例 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 4 4\n10 20 30 40\nabcb\ncabc\nabbb\ncccc\nababacabaabcca\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e146386692\n32395942\n146386694\n32395944\n146386696\n851050282\n242422295\n512573933\n146386700\n146386701\n32395951\n66073407\n572924730\n242422302\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}