eolymp
bolt
Try our new interface for solving problems

Queue

Time limit 1 second
Memory limit 256 MiB

Few programmers know that queues exist in real life and not only in Computer Science. One day, n people formed a queue to buy something very important. However, the Place in front of which they gathered was still closed. In the boredom people started going back and forth, someone even left. As a result, when the Place finally opened the queue messed up badly. Only k people out of n still remained. Some of these k people remember the name of the person who stood right before them; some remember the name of the person who stood right after them. After gathering all available information you need to determine in how many ways you can restore the queue without contradicting to the things that people remember. Two ways are considered to be different if there are at least two people appearing in different order to each other.

Input data

The first line of input contains two integers n and k (1kn50000) - the number of people who were in the queue initially, and how many of them left afterwards. The following k lines contain the names of people who remained. In the next line there is an integer q (1q100000) - the number of available pieces of information. Next q lines describe these pieces. Each line has one of the following formats:

  • after <name1> <name2> - means that a person named <name1> remember that a person named <name2> stood right after him in the queue;

  • before <name1> <name2> - means that a person named <name1> remember that a person named <name2> stood right before him in the queue.

Here <name1> is the name of the person who remains, but person with name <name2> may have left. Also <name2> can be "nobody", which means that person named <name1> remembers that nobody stood right after of right before him (so he was the last or the first in the queue). The same person can remember several things. Different people have different names. The total number of different names does not exceed n. Each name consists of 3 to 10 small Latin letters. No person can have a name "nobody".

Output data

Print the number of ways you can restore the queue, taking into account the information people remember, modulo 10^9+7. Note that given information can be contradictory. In this case print "0".

Examples

Input example #1
1314 1185
vwtsftlh
rvc
ukl
fpgujofa
amac
iexwm
gnc
myya
ozv
niffqfl
qjvtwfzpr
aykrct
ngw
hjyhmjuq
gwuv
vajn
plmnjp
nvrqfel
tipk
wlbayzp
wobjusdgvz
ymkevs
fxehj
ntpahov
onumgujcw
hxq
ghpr
fcyq
szqphsvkiq
povxeh
gar
cciful
nihhzrv
rny
ipmhynvfc
qvi
drhiheth
cmyonqtfca
tvvfz
qrboyakphl
jzumb
ljk
hgjwfcka
rmfzwb
emhy
zqhw
mgrkwnpr
zgdsghwkvp
qqayf
yuxkzgj
xneyklaeqh
lrpzq
tvu
njekaechiz
gyqyzci
cstabx
qfnjusqicr
sqyrnwjx
qyijxgq
vnehbxcu
mnvpebzmy
bqgi
kkzzsbzsk
xyp
agp
ngkuoyaro
lxelge
eapofgbx
mgerzjfg
urdtdrcrvz
uszwvspr
hpnkbqhg
qospwipn
hqz
nmfdpc
xrd
kehyqkzp
eeycqs
ynosagdxov
ntosrdkr
sjwcayvrw
uagarkufk
tdnrbxi
dxk
nkaai
svn
mcheecahjx
dumby
muoovnxhtt
hgce
shcpia
osxaavsn
izvki
wdnzjf
vlynhte
udx
dlfdmpsw
hywcavuqfv
hnxpxdibs
qnoksunphp
hshvylvos
cgslnzps
iiotlvgq
awthf
fwudpwr
mzdl
qvyej
vshzxaozbr
dstcntn
rbtebzrhth
noxmrdgln
jsfot
djngdscwkk
dovabrl
tlfueighi
nlbwuu
ouzysmv
mjgnsw
tmcux
umb
enysnpz
ywgu
xnm
amdkwjbhy
mwe
jewwng
nnpbhawox
yqrzwap
wixd
toetjmm
umwb
kyoex
fylaojyj
...
Output example #1
479001600
Source ACM-ICPC Ukraine 2012, 2nd Stage Ukraine, September 6, 2012