The problem statement has recently been changed. View the changes.

×
G. Monkey's Keyboard

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputOnce 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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/03/2023 14:17:23 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|