Migrated from Lutece 2447 复读机的新游戏2

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

前期工作已经准备就绪，复读机在群聊中玩玩新游戏试探一下。

• 复读机1：一开口就是老套娃了
• 复读机2：一开口就是一开口就是老套娃了
• 复读机3：一开口就是一开口就是一开口就是老套娃了
• 复读机4：一开口就是一开口就是一开口就是一开口就是老套娃了
• 复读机4已被管理员禁言30天

复读机制定了特殊的游戏规则，每一个复读机的发言必须是回文串，第 $i$ 个复读机在复读的时候总是会找到第 $i-1$ 个复读机的发言$S$（第一个复读机找到发言$S$为空串），不断在S的开头添加字符 $c$，使得$S:=c+S$（+代表字符串拼接），直到 $S$ 是一个回文串，然后这个复读机将添加字符后的 $S$ 作为自己的发言发送，每个复读机只会发言一次，复读机的编号按发言顺序排列，复读机发言必定是回文串，每次发言至少添加一个字符。

管理员发现了复读机的游戏，准备研究这一群复读机的快乐值，由此指定合理的抵抗策略。为了评定复读机发言的快乐值，他们连夜制定了一套标准。若设第 $i$ 个复读机的快乐值为 $a_i$ ，字符 $c$ 的快乐值为 $V_c$ ，添加字符构成的前缀为 $c_1c_2c_3...c_n$ ，那么第 $i$ 个复读机的快乐值满足 $a_i = a_{i-1}*2 + \sum_{i= 1}^{n} V_{c_i}$

现在管理员得到了群聊记录 $T$， 它仅由小写字母 a-z 组成。管理员希望你帮忙找到其中所有可能是复读机发送的发言，输出这些发言的快乐值总和对 1000000007 取模的值。

Input

第一行包含一个字符串 $T(1\le |T| \le 10^6)$ ，代表得到的群聊记录

第二行包含26个整数，第 1 个整数 $V_1$ 代表字符 $a$ 的快乐值，第 2 个整数 $V_2$ 代表字符 $b$ 的快乐值，以此类推，$0 \le V_i \le 2^{31}-1$

Output

输出一个对 1000000007 取模的整数代表答案

Samples

aba
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

7

abaaba
1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

43

Note

样例解释 aba包含回文串 a, b, aba， 其中a出现2次，b出现1次，aba出现一次 a价值为1，b价值为1，aba价值为4 总体价值2 x 1 + 1 + 4 = 7

Resources

2020 UESTC ICPC Training for String and Search Algorithm