Migrated from Lutece 2614 naive string problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

一个猴子在给一个初始为空的字符串中打入新的小写英文字符。给定每个字符的初始概率权重 $p_i$ ，则按英文字母顺序，第 $i$ 个小写英文字符被打出来的概率为 $\large \frac{p_i}{\sum p_j}$。

现在给定一个字符串 $s$，询问 $s$ 的所有子串被打出来的期望时间的和。

「被打出来」是指：假设猴子当前打出的字符串是 $t$，则字符串 $s$ 被打出当且仅当 $s$ 是 $t$ 的后缀且 $s$ 在 $t$ 中第一次出现。

Input

第一行一个字符串 $s$。 第二行 $13$ 个数字表示前 $13$ 个字母的权重。 第三行 $13$ 个数字表示后 $13$ 个字母的权重。

Output

输出答案对 $10^9+7$ 取模之后的结果。

Samples

sugar
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

12850890

ssugarr
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

687205874

Constraints

$1\leq |s|\leq 5\times 10^5$ $1\leq p_i\leq 5\times 10^5$ 题目中的所有字符都为小写英文字母。

Note

搞成两行只是方便看而已，一起输入就行。

Resources

2021 UESTC ICPC Training for String and Search Algorithm