{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eIt\u0027s known to all that ZYB is godlike, so obviously he has a large number of titles, such as $\\texttt{jsking}$, $\\texttt{bijingzyb}$ and $\\texttt{nbazyb}$. ZYB likes his titles very much.\u003cbr\u003e\u003cbr\u003eEach of ZYB\u0027s titles is a string consisting of lower case letters $\\texttt{\u0027a\u0027-\u0027z\u0027}$ associated with a happiness value $h_i$, which shows how much ZYB likes this title. If you say any substring of some title with happiness value $x$, he will get $x$ happiness points. Moreover, a string may appear in more than one title. In this case, the happiness points ZYB gets are multiplied. If the string you say is not the substring of any of his titles, he gets no happiness point.\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/3dfff36e75d609031aa9f04bebc491e7?v\u003d1716064245\"\u003e\u003c/center\u003e\u003cbr\u003e\u003cbr\u003eFor example, let\u0027s say ZYB has two titles: $\\texttt{zybnb}$ (with happiness value 3) and $\\texttt{ybyb}$ (with happiness value 5). If you say $\\texttt{y}$, $\\texttt{b}$ or $\\texttt{yb}$, ZYB will get 15 happiness points; if you say $\\texttt{z}$, $\\texttt{zy}$ or $\\texttt{zyb}$, ZYB will only get 3 happiness points; if you say $\\texttt{ybz}$ or $\\texttt{ybac}$ he will get 0 happiness points.\u003cbr\u003e\u003cbr\u003eOne day, you find ZYB pretty sad. As a big fan of ZYB, you want to say a word to ZYB to cheer him up. However, ZYB is really busy, so you can only say no more than $m$ letters. As you haven\u0027t seen ZYB for a long time, you are so excited that you forget what you want to say, so you decide to choose to say a nonempty string no longer than $m$ and only containing $\\texttt{\u0027a\u0027-\u0027z\u0027}$ with equal probability. You want to know the expectations of happiness points you will bring to ZYB for different $m$.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $n$ $(1 \\leq n \\leq 10^4)$, the number of titles ZYB has.\u003cbr\u003e\u003cbr\u003eThe $i$-th of the next $n$ lines contains a nonempty string $t_i$, which only contains lower case letters $\\texttt{\u0027a\u0027-\u0027z\u0027}$, representing the $i$-th title. The sum of lengths of all titles does not exceed $3 \\times 10^5$.\u003cbr\u003e\u003cbr\u003eThen follows a line with $n$ integers $h_i$ $(1\\leq h_i \\leq 10^6)$, the happiness value of $i$-th title.\u003cbr\u003e\u003cbr\u003eThe next line is a single integer $Q$ $(1 \\leq Q \\leq 3 \\times 10^5)$, the number of queries.\u003cbr\u003e\u003cbr\u003eFor the next $Q$ lines, each contains a single integer $m$ $(1 \\leq m \\leq 10^6)$, meaning that you can say no more than $m$ letters to ZYB.\u003cbr\u003e\u003cbr\u003eThe input data contains only one test case."}},{"title":"Output","value":{"format":"HTML","content":"For each query, display a single line of integer, representing the answer. It can be proved that the answer can be uniquely written as $p/q$ where $p$ and $q$ are non-negative integers with $\\gcd(p, q) \u003d \\gcd(q, 10^9 + 7) \u003d 1$, and you should display $p \\cdot q^{-1} \\bmod (10^9 + 7)$, where $q^{-1}$ means the multiplicative inverse of $q$ modulo $10^9 + 7$."}},{"title":"Sample","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\r\nzybnb\r\nybyb\r\n3 5\r\n4\r\n1\r\n2\r\n3\r\n4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e769230776\r\n425925929\r\n891125950\r\n633120399\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eFor the first query, you can bring him 3 happiness points if you say \"z\" or \"n\", and 15 happiness points if you say \"y\" or \"b\"; all other strings of length 1 bring no \u003cbr\u003ehappiness point to ZYB. Therefore, the expectation is (2×3+2×15)/26 \u003d 18/13, and the answer is 18×13^(-1) mod (10^9+7) \u003d 769230776.\u003cbr\u003e"}}]}