Queue
Queue
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 (1 ≤ k ≤ n ≤ 50000) - 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 (1 ≤ q ≤ 100000) - 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
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 ...
479001600