题目概述

• 时间限制：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 无特殊限制