Növbə#3760
Bir çox proqramçı bilir ki, növbələr yalnız Kompüter Elmlərində deyil, real həyatda da mövcuddur. Bir gün, n nəfər çox vacib bir şey almaq üçün növbə təşkil etdi. Lakin, onların toplandığı yer hələ bağlı idi. Darıxan insanlar irəli-geri getməyə başladılar, hətta bəziləri getdi. Nəticədə, yer nəhayət açıldığında növbə pis şəkildə qarışdı. Yalnız k nəfər n nəfərdən hələ də qaldı. Bu k nəfərdən bəziləri onların qarşısında kimin dayandığını xatırlayır; bəziləri isə arxasında kimin dayandığını xatırlayır. Mövcud bütün məlumatları toplayaraq, insanların xatırladıqlarına zidd olmadan növbəni neçə yolla bərpa edə biləcəyinizi müəyyən etməlisiniz. İki yol fərqli hesab olunur, əgər ən azı iki nəfər bir-birinə nisbətən fərqli sırada görünürsə.
Girişin ilk sətri iki tam ədəd n və k (1 ≤ k ≤ n ≤ 50000) - növbədə əvvəlcə olan insanların sayı və sonradan qalanların sayı. Növbəti k sətir qalan insanların adlarını ehtiva edir. Növbəti sətirdə q (1 ≤ q ≤ 100000) - mövcud məlumat parçalarının sayı. Növbəti q sətir bu parçaları təsvir edir. Hər sətir aşağıdakı formatlardan birinə malikdir:
after <name1> <name2> - bu, <name1> adlı şəxsin xatırladığını bildirir ki, <name2> adlı şəxs növbədə onun dərhal arxasında dayanmışdı;
before <name1> <name2> - bu, <name1> adlı şəxsin xatırladığını bildirir ki, <name2> adlı şəxs növbədə onun dərhal qarşısında dayanmışdı.
Burada <name1> qalan şəxsin adıdır, lakin <name2> adlı şəxs getmiş ola bilər. Həmçinin <name2> "nobody" ola bilər, bu isə <name1> adlı şəxsin xatırladığını bildirir ki, onun dərhal arxasında və ya qarşısında heç kim dayanmırdı (yəni o, növbədə birinci və ya sonuncu idi). Eyni şəxs bir neçə şeyi xatırlaya bilər. Fərqli insanların fərqli adları var. Fərqli adların ümumi sayı n-dən çox deyil. Hər ad 3 ilə 10 kiçik Latın hərfindən ibarətdir. Heç bir şəxsin adı "nobody" ola bilməz.
İnsanların xatırladıqlarını nəzərə alaraq növbəni neçə yolla bərpa edə biləcəyinizi, 10^9+7 modulu ilə çap edin. Qeyd edək ki, verilən məlumatlar ziddiyyətli ola bilər. Bu halda "0" çap edin.
Nümunə 1