题目描述

一天 小珅造访了猫猫国，猫猫国的每个单词都是由小写英文字母构成的，长度都恰好为 4。小珅 在猫猫国看到了一段话，想要弄清楚这段话的含义就有点困难了，于是小珅 希望你来帮他翻译一下。

这段话一共包含 $n$个猫猫国单词，第 $i$个单词是 $s_i$。为了帮你翻译，小珅 还给了你猫猫国词典，包含了 $m$个单词的含义，每个单词的含义都由一些猫猫国单词构成。

小珅希望你从前往后，每遇到一个猫猫国词典中存在的单词，就把这个单词替换为词典中对应的含义。显然含义中如果包含了猫猫国词典中的单词也继续替换。直到无法再替换了为止。

由于最终的译文可能很长，你只需要输出译文中所有小写英文字母对应的 ASCII 码之和对 $10^9 + 7$取模后的结果即可。

输入格式

第一行包含两个整数 $n, m$，含义如题意所述。

第二行为 $n$个空格隔开的猫猫国单词，即需要翻译的句子。

接下来 $m$行，每行首先输入一个字符串，即词典中的某个猫猫国单词。然后一个整数 $num$表示在这个单词的含义由几个单词构成。然后是 $num$个空格隔开的猫猫国单词。

输出格式

输出一个整数，即题目要求的内容。

输入输出样例

输入 #1

7 3 good isxx badx andx badx isxx good badx 2 orxx xorx good 3 badx orxx badx orxx 1 okxx

输出 #1

7801

输入 #2

1 25 axxx axxx 5 bxxx bxxx bxxx bxxx bxxx bxxx 5 cxxx cxxx cxxx cxxx cxxx cxxx 5 dxxx dxxx dxxx dxxx dxxx dxxx 5 exxx exxx exxx exxx exxx exxx 5 fxxx fxxx fxxx fxxx fxxx fxxx 5 gxxx gxxx gxxx gxxx gxxx gxxx 5 hxxx hxxx hxxx hxxx hxxx hxxx 5 ixxx ixxx ixxx ixxx ixxx ixxx 5 jxxx jxxx jxxx jxxx jxxx jxxx 5 kxxx kxxx kxxx kxxx kxxx kxxx 5 lxxx lxxx lxxx lxxx lxxx lxxx 5 mxxx mxxx mxxx mxxx mxxx mxxx 5 nxxx nxxx nxxx nxxx nxxx nxxx 5 oxxx oxxx oxxx oxxx oxxx oxxx 5 pxxx pxxx pxxx pxxx pxxx pxxx 5 qxxx qxxx qxxx qxxx qxxx qxxx 5 rxxx rxxx rxxx rxxx rxxx rxxx 5 sxxx sxxx sxxx sxxx sxxx sxxx 5 txxx txxx txxx txxx txxx txxx 5 uxxx uxxx uxxx uxxx uxxx uxxx 5 vxxx vxxx vxxx vxxx vxxx vxxx 5 wxxx wxxx wxxx wxxx wxxx wxxx 5 xxxx xxxx xxxx xxxx xxxx xxxx 5 yxxx yxxx yxxx yxxx yxxx yxxx 5 zxxx zxxx zxxx zxxx zxxx

输出 #2

161055929

说明/提示

对于 $100\%$的数据：

保证 $1 \le n \le 10^5$，$0 \le m \le 10^5$

保证能翻译完，即能翻译成不会有任何单词能在词典中找到含义的句子。

保证词典中的每个单词的含义不超过 5 个单词。

子任务划分

子任务 1（$10$分）：保证 $m = 0$

子任务 2（$20$分）：保证词典中每个单词的含义里没有词典中的其他单词。

子任务 3（$30$分）：保证最终翻译结果不超过 $1000$个单词。

子任务 4（$40$分）：没有特殊限制。

样例一解释：

翻译句子的流程是（小括号是便于理解得辅助记号，不是译文的内容）：

• good isxx badx andx badx isxx good

• (badx orxx badx) isxx badx andx badx isxx (badx orxx badx)

• (orxx xorx) orxx (orxx xorx) isxx (orxx xorx) andx (orxx xorx) isxx (orxx xorx) orxx (orxx xorx)

• okxx xorx okxx okxx xorx isxx okxx xorx andx okxx xorx isxx okxx xorx okxx okxx xorx

5 18
aaaa baaa wdaa omba zdaa
aaaa 2 caaa daaa
baaa 2 caaa daaa
caaa 2 eaaa faaa
daaa 2 eaaa faaa
eaaa 2 gaaa haaa
faaa 2 gaaa haaa
gaaa 2 iaaa jaaa
haaa 2 iaaa jaaa
iaaa 2 kaaa laaa
jaaa 2 kaaa laaa
kaaa 2 maaa naaa
laaa 2 maaa naaa
maaa 2 oaaa paaa
naaa 2 oaaa paaa
oaaa 2 qaaa raaa
paaa 2 qaaa raaa
qaaa 2 saaa taaa
raaa 2 saaa taaa

417500

40 49
aaaa baaa caaa daaa eaaa faaa gaaa haaa iaaa jaaa kaaa laaa maaa naaa oaaa paaa qaaa raaa saaa taaa uaaa vaaa waaa xaaa yaaa zaaa abaa bbaa cbaa dbaa ebaa fbaa gbaa hbaa ibaa jbaa kbaa lbaa mbaa nbaa
aaaa 5 aeaa ydaa ydaa deaa beaa
baaa 5 feaa ydaa eeaa beaa zdaa
caaa 5 ceaa deaa deaa wdaa ceaa
daaa 5 zdaa xdaa beaa zdaa beaa
eaaa 5 feaa ydaa deaa ydaa wdaa
faaa 5 wdaa xdaa xdaa deaa aeaa
gaaa 5 xdaa eeaa ceaa xdaa ceaa
haaa 5 beaa beaa eeaa ydaa ydaa
iaaa 5 zdaa eeaa ceaa zdaa eeaa
jaaa 5 deaa ydaa deaa aeaa xdaa
kaaa 5 feaa feaa xdaa deaa xdaa
laaa 5 beaa ceaa zdaa deaa wdaa
maaa 5 ydaa feaa ydaa ceaa deaa
naaa 5 zdaa xdaa eeaa wdaa deaa
oaaa 5 xdaa deaa beaa beaa ydaa
paaa 5 beaa wdaa deaa aeaa aeaa
qaaa 5 beaa beaa beaa ydaa deaa
raaa 5 feaa deaa xdaa xdaa xdaa
saaa 5 eeaa eeaa deaa eeaa wdaa
taaa 5 ceaa ydaa eeaa deaa xdaa
uaaa 5 xdaa ydaa ydaa deaa xdaa
vaaa 5 xdaa eeaa xdaa zdaa xdaa
waaa 5 ceaa zdaa feaa eeaa aeaa
xaaa 5 eeaa ydaa beaa wdaa ydaa
yaaa 5 aeaa aeaa zdaa xdaa ceaa
zaaa 5 xdaa ydaa beaa wdaa wdaa
abaa 5 beaa beaa deaa aeaa eeaa
bbaa 5 zdaa deaa ydaa aeaa zdaa
cbaa 5 beaa beaa zdaa deaa ydaa
dbaa 5 aeaa zdaa wdaa wdaa aeaa
ebaa 5 beaa ydaa ydaa ceaa deaa
fbaa 5 deaa zdaa deaa beaa beaa
gbaa 5 ydaa wdaa xdaa deaa deaa
ibaa 5 aeaa aeaa ceaa feaa zdaa
jbaa 5 feaa xdaa feaa zdaa eeaa
kbaa 5 ceaa xdaa wdaa eeaa deaa
lbaa 5 ydaa xdaa deaa feaa eeaa
mbaa 5 aeaa eeaa aeaa deaa eeaa
nbaa 5 ceaa xdaa aeaa wdaa xdaa
wdaa 5 goca uxca zdca yyca poba
xdaa 5 fwca fmca vmba boba vpca
ydaa 5 ovba ixca ssba csba dsba
zdaa 5 yrba gcca owca fxca hsca
aeaa 5 ryca zuba daca occa ymba
beaa 5 lica ntca lhca iaca guca
ceaa 5 wmca dqba poca lnba ooba
deaa 5 okca ikca ipca nxca omba
eeaa 5 vsca ktba xxba qvca anba
feaa 5 ifca ehca pdca vgca ayba

406406

200 200
aaaa baaa caaa daaa eaaa faaa gaaa haaa iaaa jaaa kaaa laaa maaa naaa oaaa paaa qaaa raaa saaa taaa uaaa vaaa waaa xaaa yaaa zaaa abaa bbaa cbaa dbaa ebaa fbaa gbaa hbaa ibaa jbaa kbaa lbaa mbaa nbaa obaa pbaa qbaa rbaa sbaa tbaa ubaa vbaa wbaa xbaa ybaa zbaa acaa bcaa ccaa dcaa ecaa fcaa gcaa hcaa icaa jcaa kcaa lcaa mcaa ncaa ocaa pcaa qcaa rcaa scaa tcaa ucaa vcaa wcaa xcaa ycaa zcaa adaa bdaa cdaa ddaa edaa fdaa gdaa hdaa idaa jdaa kdaa ldaa mdaa ndaa odaa pdaa qdaa rdaa sdaa tdaa udaa vdaa wdaa xdaa ydaa zdaa aeaa beaa ceaa deaa eeaa feaa geaa heaa ieaa jeaa keaa leaa meaa neaa oeaa peaa qeaa reaa seaa teaa ueaa veaa weaa xeaa yeaa zeaa afaa bfaa cfaa dfaa efaa ffaa gfaa hfaa ifaa jfaa kfaa lfaa mfaa nfaa ofaa pfaa qfaa rfaa sfaa tfaa ufaa vfaa wfaa xfaa yfaa zfaa agaa bgaa cgaa dgaa egaa fgaa ggaa hgaa igaa jgaa kgaa lgaa mgaa ngaa ogaa pgaa qgaa rgaa sgaa tgaa ugaa vgaa wgaa xgaa ygaa zgaa ahaa bhaa chaa dhaa ehaa fhaa ghaa hhaa ihaa jhaa khaa lhaa mhaa nhaa ohaa phaa qhaa rhaa
aaaa 5 tjca zoba wjca oxba bnca
baaa 5 ipba pmba euca dkca bqca
caaa 5 jpba kaca qhca cbca ioca
xhaa 5 ijca hsba hnba zcca oeca
eaaa 5 inca azba csba lvba qoba
faaa 5 upba zpba jkca exca mhca
gaaa 5 ooba qmca arba pjca qlca
haaa 5 jgca onca shca yyba jvca
iaaa 5 pjca ehca fjca krca vpba
jaaa 5 zbca cqba ypca otca jrba
kaaa 5 gwca exba cpba geca evca
laaa 5 jsba vdca lzba knba jcca
maaa 5 jtca osca vvba gqca euca
naaa 5 gmca ltca wpca hvca vpca
oaaa 5 duba lyca fpca kxca qeca
paaa 5 isca owba omba wfca xeca
qaaa 5 rqba jeca fsca woca kuca
raaa 5 nrca etba ckca qica owca
saaa 5 irba tqca ptca vrba pgca
taaa 5 oyca wvca muca uoba guca
uaaa 5 tnba hyba jbca ktba mpba
vaaa 5 loca tyba yaca otca zpba
waaa 5 qwca jgca wrba ynba boca
xaaa 5 vrca eeca euca uwca vyba
yaaa 5 ptba pfca ipba kica tkca
zaaa 5 tvca otba keca djca byca
abaa 5 bvba yvca obca zxba evca
bbaa 5 zcca ouca xzba luba mpca
cbaa 5 umba gkca rtca wjca ywba
dbaa 5 sjca anba ivba oeca oqca
ebaa 5 ljca tgca gxba bica rnca
fbaa 5 wmba nqca xnba zyba ouca
gbaa 5 cnba raca rjca igca cyba
hbaa 5 nica ieca hqba koba ypba
ibaa 5 jrca jqca jsca kmca soba
jbaa 5 yqba geca kpba hqba zxca
kbaa 5 ssca xqba otba yjca ntca
lbaa 5 nrba tkca oxca fsba mfca
mbaa 5 vlca nxba ykca qnba dlca
nbaa 5 wvca svba szba lpba elca
obaa 5 mxca cwba wqba gcca lyca
pbaa 5 rwca prca psca bpca ayca
qbaa 5 xrba ayca ygca anca vmba
rbaa 5 bbca vqba xoca isba kuba
sbaa 5 maca mica uuca jrba ieca
tbaa 5 jqba vmca wxba veca euca
ubaa 5 ofca oica prba xwca pvba
vbaa 5 rgca ewba rrca fwca nnca
wbaa 5 zmca gnca reca vrca hjca
xbaa 5 brba fpba xeca rnca crca
ybaa 5 qtca ryca gvca jqca owba
zbaa 5 esca prba zoca kuca boba
acaa 5 ayca lyba nqca toba tvba
bcaa 5 eeca enba dpca dyca fbca
ccaa 5 apca pwca nyca aqba koba
dcaa 5 grba euca tmca spca jtca
ecaa 5 kpba puba xsba oeca wxca
fcaa 5 rtba dkca noca lhca zdca
gcaa 5 naca boca qyca ozba tqca
hcaa 5 qtca znca dpba zmca ugca
icaa 5 tyba gcca ywca gcca jnba
jcaa 5 yyba dpca zmca keca isca
kcaa 5 fuba kyba evba vrba poba
lcaa 5 hlca yoca vaca xlca ikca
mcaa 5 ylca cxba ucca pxba foca
ncaa 5 qsba vmca saca glca gvca
ocaa 5 jnba afca jnca bzba rnca
pcaa 5 ewba crca baca boba cnca
qcaa 5 vmca nwca huba acca zcca
rcaa 5 ldca dbca hfca wrba uqba
scaa 5 xlca krca ecca keca nmba
tcaa 5 oaca svca jica xkca zcca
ucaa 5 gmca uyba jcca jpca hwba
vcaa 5 swba awca syba kpba lkca
wcaa 5 pqba fwca fuba mtba msba
xcaa 5 tqca pmba nmba htba yfca
ycaa 5 lnba zqba rwba poca dkca
zcaa 5 nqca uyca zhca jvca otca
adaa 5 llca vvba luba haca zwca
bdaa 5 qpca mfca qhca utba elca
cdaa 5 hvba ghca cwca hoca vfca
ddaa 5 ndca jyca cxba xsba sica
edaa 5 jnba lsca dmca ztba tqca
fdaa 5 csca lyba ztca hbca jaca
gdaa 5 vyba fsca qxca tgca uqba
hdaa 5 roba itba wvba feca xqba
idaa 5 evba aoca nxca zdca drba
jdaa 5 bica kkca fuca lgca ynba
kdaa 5 uxba asba inba nfca reca
ldaa 5 qnca fwca enba cfca lzba
mdaa 5 ecca rrba fqca nhca vxca
ndaa 5 lkca yuca vhca zeca mnca
odaa 5 lfca mxba crca smba yuca
pdaa 5 ebca xtba fmca enca ahca
qdaa 5 iqca wsca unca doca msca
rdaa 5 yica fcca nlca jjca jyba
sdaa 5 yyca flca uzba sxca rlca
tdaa 5 wnca cyca fdca daca pzba
udaa 5 ypba zqca dyba jxca ygca
vdaa 5 inba whca nnba pyba axca
wdaa 5 uuba ysba ztca ukca btca
xdaa 5 jkca lqba ceca arba njca
ydaa 5 kxba oyba tmca gvca feca
zdaa 5 reca otba ckca xnba isba
aeaa 5 rfca zvca yica slca sbca
beaa 5 rxca phca cbca qzba qrca
ceaa 5 kjca avca ojca ntba isca
deaa 5 zkca wwca fsca epca boca
eeaa 5 knca jaca koca kzba heca
feaa 5 oeca ejca xpba zuca omca
geaa 5 kbca mmca tnca lica bpca
heaa 5 euba unca zyba ylca wpba
ieaa 5 htba jcca vica fwca vyba
jeaa 5 uwba twca hwba emca zjca
keaa 5 dyba lyca cmca obca qaca
leaa 5 lhca qsca mzba aeca osba
meaa 5 uaca uoca htca wcca kjca
neaa 5 zmba fqba edca utca ieca
oeaa 5 ehca bqca ilca rxca osba
peaa 5 voca bpba rjca pnca uoba
qeaa 5 rrba upba gtca wwca ltba
reaa 5 tvca xrba ipba tpba vmba
seaa 5 mvca doca svca seca buca
teaa 5 nqca avba amca heca uyca
ueaa 5 buca xyba wpca obca pxba
veaa 5 ahca frca atba ztba jpba
weaa 5 nnca xlca vqca ctba lica
xeaa 5 vmca ehca bxba hqba moca
yeaa 5 jrba btba fwca rsba dwba
zeaa 5 fhca ywca qtba sgca voca
afaa 5 owba tpca tfca dyca oxca
bfaa 5 qkca inba hlca rrca lnca
cfaa 5 yyba bwba ffca onba bvca
dfaa 5 smca upba itca bwba nqca
efaa 5 inba xxba wwba fjca zbca
ffaa 5 hyba plca srba uxca rica
gfaa 5 sqba yaca yvba qaca qmca
hfaa 5 suba rpba gxca elca vgca
ifaa 5 zoca nrca mrca utba ntba
jfaa 5 puca kjca teca phca jica
kfaa 5 oqca teca ylca aica fdca
lfaa 5 mqca fhca upba jwba vsca
mfaa 5 mbca cwca bbca sqca ljca
nfaa 5 bqba knca bsba bpba ttba
ofaa 5 jwba iaca utca ooca oqca
pfaa 5 xnba zqba cnca fhca rsba
qfaa 5 arca pzba enba uoba rsca
rfaa 5 pxba phca xwca usba nfca
sfaa 5 wqba saca qrca syca jpca
tfaa 5 gbca bnca vica zuba kmca
ufaa 5 rrca goba ppca snca tkca
vfaa 5 ntba yxba cvca drca vyca
wfaa 5 mxba tkca paca tsba rnba
xfaa 5 efca nbca nsba znba joca
yfaa 5 fnba fvca ncca vica uzba
zfaa 5 ipca msca srca tmba elca
agaa 5 upba ntca bzba ofca maca
bgaa 5 zqba esba dzba fkca fmca
cgaa 5 hwca vuba lrba ppba rnba
dgaa 5 bhca oyba gzba bsca gwba
egaa 5 krca vqca esca roba mgca
fgaa 5 rtca orca rsca qpca gfca
ggaa 5 ykca kpba bxca quba jxca
hgaa 5 olca pvba wuca ayba huca
igaa 5 sica spba fmca yvba uoba
jgaa 5 qvba juba ikca pkca uvca
kgaa 5 qyca umba xxba jkca ycca
lgaa 5 bhca kmca byca ljca puba
mgaa 5 upba myca mvba cuca xqca
ngaa 5 fnba poca iica oica gxca
ogaa 5 jcca lvca nvba qwba ewba
pgaa 5 sgca rtba taca kyba ynca
qgaa 5 hnba ikca fqba vzba rrba
rgaa 5 hrca qmba ijca rbca hrca
sgaa 5 moba fwba vtba dpba ioca
tgaa 5 xjca vyba gdca noca nzba
ugaa 5 jzba fgca qaca abca njca
vgaa 5 lhca omba ftca huba xjca
wgaa 5 kzba kbca xnca haca kdca
xgaa 5 guca ruba wpca tsca xrba
ygaa 5 swca lhca brba heca klca
zgaa 5 psca omba ltca tvca gaca
ahaa 5 hjca vgca ewba qnca dzba
bhaa 5 rvba osca bdca zoba weca
chaa 5 aica naca ucca ezba wjca
dhaa 5 nnca qeca cwca zvba tpca
ehaa 5 pnba owba grba ftca reca
fhaa 5 bqca bsba dyba ieca zxba
ghaa 5 wlca orba kcca ljca iqca
hhaa 5 fuca fxca yoca qwba ypba
ihaa 5 udca hsba cyba hnba ymba
jhaa 5 juba kxca ssca osca yqca
khaa 5 zmca xpba wqca drca tjca
lhaa 5 isba byca wica vdca luba
mhaa 5 ilca bxba dsca cuba jjca
nhaa 5 ljca uwba aoba uvca alca
ohaa 5 glca dsca imca pfca lfca
phaa 5 wyca pxba doba fnca zsca
qhaa 5 baca tgca xtba oaca ntba
rhaa 5 wwca psba osca qwca nyba

415049