Черга#3760

Черга

1 секунда

256 мегабайтів

Складна

Багато програмістів не знають, що черги існують не лише в інформатиці, а й у реальному житті. Одного разу $n$ людей зібралися в чергу, щоб придбати щось дуже важливе. Проте місце, де вони зібралися, ще не відкрилося. Від нудьги люди почали переміщатися, а дехто навіть пішов. У результаті, коли місце нарешті відкрилося, черга була сильно переплутана. Лише $k$ з $n$ людей залишилися. Деякі з цих $k$ людей пам'ятають, хто стояв прямо перед ними, а деякі — хто стояв прямо за ними. Зібравши всю доступну інформацію, вам потрібно визначити, скількома способами можна відновити чергу, не суперечачи тому, що пам'ятають люди. Два способи вважаються різними, якщо є принаймні дві людини, які з'являються в різному порядку одна відносно одної.

Вхідні дані

Перший рядок вхідних даних містить два цілі числа $n$ та $k$ ( $1 \leq k \leq n \leq 50000$ 1 \leq k \leq n \leq 50000) — кількість людей, які спочатку були в черзі, і скільки з них залишилося потім. Наступні $k$ рядків містять імена людей, які залишилися. У наступному рядку знаходиться ціле число $q$ ( $1 \leq q \leq 100000$ 1 \leq q \leq 100000) — кількість доступних шматків інформації. Наступні $q$ рядків описують ці шматки. Кожен рядок має один з наступних форматів:

after <name1> <name2> — означає, що людина на ім'я <name1> пам'ятає, що людина на ім'я <name2> стояла прямо за нею у черзі;
before <name1> <name2> — означає, що людина на ім'я <name1> пам'ятає, що людина на ім'я <name2> стояла прямо перед нею у черзі.

Тут <name1> — це ім'я людини, яка залишилася, але людина з ім'ям <name2> могла піти. Також <name2> може бути "nobody", що означає, що людина на ім'я <name1> пам'ятає, що ніхто не стояв прямо за нею або прямо перед нею (тобто вона була останньою або першою у черзі). Та сама людина може пам'ятати кілька речей. Різні люди мають різні імена. Загальна кількість різних імен не перевищує $n$ . Кожне ім'я складається з $3$ до $10$ малих латинських літер. Жодна людина не може мати ім'я "nobody".

Вихідні дані

Виведіть кількість способів, якими можна відновити чергу, враховуючи інформацію, яку пам'ятають люди, за модулем $1 0^{9} + 7$ 10^9+7. Зверніть увагу, що надана інформація може бути суперечливою. У цьому випадку виведіть "0".

Приклади

Приклад 1