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
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
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".