G. Monkey's Keyboard
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Once there was a monkey, who was smart enough to press keys on a keyboard. However, he could not understand what he pressed. One day, a computer idiot came to the monkey for help. He needed to type a chapter of Complete Works of Shakespeare, denoted as a string $$$s$$$. When the monkey kept typing, he focused on the screen. As long as the chapter he wanted occurred on the screen as a substring, he would stop the monkey immediately and gain his result using ctrl-c and ctrl-v.

For simplicity, we assume that the keyboard only consisted of $$$26$$$ lowercase English characters, and the computer idiot didn't care about spaces, punctuation and capitalization, so $$$s$$$ only consisted of lowercase English characters. As the monkey actually didn't understand what he was typing, he pressed the keys randomly. The probability of the key $$$\beta$$$ pressed on each type was $$$p_{\beta} / \sum_{\gamma=a}^z p_{\gamma}$$$, and independent of what had already been typed.

The computer idiot waited for the Shakespeare's work he wanted on the screen till hungry and cold, so he asked you how long he had to wait in the words of mathematical expectation. The time was measured by the number of keys pressed by the monkey.

The question seemed easy for you, and after learning the result, the computer idiot realized that he might not be able to get Shakespeare's work while alive. Therefore, he decided to get a substring of $$$s$$$. In order to make a more reasonable decision, he asked you again the same problem on every substring of $$$s$$$.

Since there are too many substrings of $$$s$$$, you only need to output the sum of the expected time on each substring.

Throughout the problem, a substring means a continuous subsequence of another string.

Input

The input consists of three lines.

The first line contains a string $$$s$$$ ($$$1 \leq |s| \leq 5 \times 10^5$$$) consisting of lowercase English characters.

Each of the next $$$2$$$ lines contains $$$13$$$ integers, $$$p_a, p_b, \dots, p_m$$$ and $$$p_n, p_o, \dots, p_z$$$ respectively ($$$1 \leq p_a, p_b, \dots, p_z \leq 5 \times 10^5$$$).

Output

Output the sum, for $$$t$$$ being every substring of $$$s$$$, the expected number of keys pressed until $$$t$$$ appeared on the screen, modulo $$$10^9 + 7$$$.

Formally, let $$$M = 10^9+7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Examples
Input
abc
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
Output
19006
Input
aabccdaabccdaa
1 2 3 4 5 6 7 8 9 10 11 12 13
14 15 16 17 18 19 20 21 22 23 24 25 26
Output
394656279