题目概述

• 时间限制：1s
• 空间限制：1GB

题目描述

星云旋转开始加速
看啊
那云中的一粒粒尘埃
有的在聚集，有的被甩出
看啊
星云最中心的那粒尘埃
仿佛正泛着光
它连结着别的尘埃
从零开始
一点点地生长

---

一个崭新的生命正在孕育，如何利用好所有的资源，选择一条未来的道路成为了现在最紧迫的命题。

随着星云的“凝结”，如今星云可以压缩成一个字符串来描述，而一种未来也可以用一个字符串集合来描述。
星云想选择最合适的未来，来充分利用现在的资源——

设星云的字符串为T，设未来字符串集合为S，T的第i个位置有一个权值$v[i]$。设S集合中的字符串的所有 前缀 组成集合P（P中不应含重复元素）。设P中元素共有$n$个。
对P中的每个串s，若s是T的一个子序列（T从前向后匹配，子序列不要求连续），且这个子序列在T中最靠前的结尾位置为x，则定义$p(s)=v[x] * len(s)$，其中$len(s)$为s的长度。若s不是T的一个子序列$p(s)=0$.

现在需要计算p(s)的平均数，即
$$avg_p={\sum_{s \in P} p(s) \over n}$$

由于数据过大，请计算模意义下的$avg_p$，保证模数是质数。保证字符串均由小写字母组成。

输入

第一行一个字符串T
第二行有$len(T)$个整数 表示T中各个位置的$v[i]$
第三行两个整数 n,K ，n表示S中的字符串数，K表示模数
接下来n行，每行一个S中的字符串

输出

输出$avg_p$模K意义下的值

样例

输入

abcba
1 2 3 4 5
2 11
aba
aca

输出

6

提示

S集合为{aba,aca}
P集合为{a,ab,aba,ac,aca}，n=5
P集合匹配T的位置分别为
a:1
ab:2
aba:5
ac:3
aca:5
则$\sum p(s)=1*1+2*2+5*3+3*2+5*3=26+15=41$
在模11意义下，由数学知识可知
$avg_p=(41/5) \pmod {11} = 6$
注：因为 $85 \equiv 41 \pmod {11}$，而$85/5=17,17\equiv 6 \pmod {11}$，所以$(41/5) \pmod {11} = 6$

数据范围

$v[i]<=10^3$
$1<=len(T)<=10^6$
$1<={\sum_{s\in S} len(s)}<=10^6$
$1<=n<=10^5$
$1<K<=10^9+7$

数据分布

1-5 $n<=20 ,len(T)<=100 ,{\sum_{s\in S} len(s)}<=100$
6-10 $n<=10^4 ,len(T)<=1000$
11-20 无特殊限制