{"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\u003eGiven a string $$$S$$$, $$$n$$$ strings $$$T_1,T_2,\\dots,T_n$$$ of length $$$m$$$ and a positive rational number sequence $$$p$$$ of length $$$k$$$ whose sum is $$$1$$$. Each string consists of only the first $$$k$$$ lowercase letters. Let\u0027s perform the following procedure: \u003c/p\u003e\u003col\u003e \u003cli\u003e If there exists $$$j$$$ $$$(1\\leq j\\leq n)$$$ such that $$$T_j$$$ is a substring of $$$S$$$, stop the procedure. \u003c/li\u003e\u003cli\u003e Append the $$$i$$$-th lowercase letter with probability $$$p_i$$$ to the end of $$$S$$$, then return to step 1. \u003c/li\u003e\u003c/ol\u003e Let\u0027s define $$$f(S;T,p)$$$ as the expected length of $$$S$$$ when the procedure stops.\u003cp\u003eIt\u0027s boring to calculate $$$f(S;T,p)$$$ for only one string $$$S$$$. To make the problem much harder, a string $$$R$$$ is given. Let\u0027s denote the prefix of $$$R$$$ of length $$$i$$$ as $$$R[1\\dots i]$$$. Your task is to calculate $$$f(R[1\\dots i];T,p)$$$ for $$$i\u003d1,2,\\cdots,|R|$$$.\u003c/p\u003e\u003cp\u003eIt can be proved that $$$f(S;T,p)$$$ is a positive rational number and it can be represented as $$$\\frac PQ$$$ with $$$\\gcd(P,Q)\u003d1$$$. It is guaranteed that $$$Q\\not\\equiv 0\\pmod{(10^9+7)}$$$ for all strings $$$S$$$ under the given $$$T$$$ and $$$p$$$ in the input. You should print the value of $$$PQ^{-1}\\mod (10^9+7)$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains three positive integers $$$n,m$$$ and $$$k$$$ ($$$1\\leq n\\leq 100$$$, $$$n\\times m\\leq 10\\,000$$$, $$$1\\leq k\\leq 26$$$).\u003c/p\u003e\u003cp\u003eThe second line contains $$$k$$$ positive integers $$$p\u0027_1,p\u0027_2\\cdots,p\u0027_k$$$. It is guaranteed that $$$p\u0027_1+p\u0027_2+\\cdots+p\u0027_k\u003d100$$$ and the probability $$$p_i$$$ equals to $$$\\frac{p\u0027_i}{100}$$$.\u003c/p\u003e\u003cp\u003eThe $$$i$$$-th line of the following $$$n$$$ lines contains a string $$$T_i$$$ of length $$$m$$$.\u003c/p\u003e\u003cp\u003eThe last line contains a string $$$R$$$ ($$$1\\leq|R|\\leq 10\\,000$$$).\u003c/p\u003e\u003cp\u003eIt is guaranteed each string consists of only the first $$$k$$$ lowercase letters and $$$Q\\not\\equiv 0\\pmod{(10^9+7)}$$$ when representing $$$f(S;T,p)$$$ as $$$\\frac PQ$$$ with $$$\\gcd(P,Q)\u003d1$$$ for all strings $$$S$$$ under the given $$$T$$$ and $$$p$$$ in the input.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOuput $$$|R|$$$ lines. The $$$i$$$-th line contains an integer representing the value of $$$f(R[1\\dots i];T,p)$$$.\u003c/p\u003e"}},{"title":"Examples","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\n"}},{"title":"","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\n"}},{"title":"","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\n"}}]}