İnək Şeiri

Bessi fermer Conun xəbəri olmadan əsl incəsənət himayədarıdır! O, bu yaxınlarda bir çox böyük şairləri öyrənməyə başlayıb və indi öz şeirlərini yazmağa çalışmaq istəyir. Bessi n söz bilir və onlardan şeirlər yaratmaq istəyir. Bessi hər bir sözünün heca uzunluğunu müəyyən edib və onları "qafiyə siniflərinə" bölüb. Hər bir söz yalnız eyni qafiyə sinifinə aid olan digər sözlərlə qafiyələnir.

Bessinin hər bir şeiri m sətirdən ibarətdir və hər bir sətir k hecadan ibarət olmalıdır. Üstəlik, Bessinin şeirləri müəyyən bir qafiyə sxeminə riayət etməlidir.

Bessi, verilən məhdudiyyətlərə uyğun olaraq neçə fərqli şeir yaza biləcəyini bilmək istəyir.

Giriş Məlumatları

Birinci sətir n (1 ≤ n ≤ 5000), m (1 ≤ m ≤ 10^5) və k (1 ≤ k ≤ 5000) ədədlərini ehtiva edir. Növbəti n sətirin hər biri iki ədəd s[i] (1 ≤ s[i] ≤ k) və c[i] (1 ≤ c[i] ≤ n) ehtiva edir. Bu, Bessinin s[i] heca uzunluğunda və c[i] qafiyə sinifinə aid bir söz bildiyini göstərir.

Son m sətir Bessinin istədiyi qafiyə sxemini təsvir edir, hər biri bir böyük hərf e[i] ehtiva edir. Eyni e[i] dəyərinə uyğun olan bütün sətirlər eyni qafiyə sinifinə aid sözlərlə bitməlidir. Fərqli e[i] dəyərlərinə malik sətirlər mütləq fərqli qafiyə siniflərinə aid sözlərlə bitməməlidir.

Çıxış Məlumatları

Bessi bu məhdudiyyətlərə uyğun olaraq neçə şeir yaza biləcəyini göstərin. Bu ədəd çox böyük ola biləcəyi üçün onu 10^9 + 7 modulu ilə hesablayın.

Nümunə

Verilən nümunədə Bessi üç söz bilir. İlk iki söz qafiyələnir və üç və dörd hecadan ibarətdir, sonuncu söz isə üç hecadan ibarətdir və digər sözlərlə qafiyələnmir. O, hər biri on hecadan ibarət olan üç sətirdən ibarət bir şeir yazmaq istəyir və birinci və sonuncu sətirlər qafiyələnməlidir. Belə şeirlərin sayı 960-dır. Bu şeirlərdən birinin nümunəsi (1, 2 və 3 birinci, ikinci və üçüncü sözü təmsil edir): 121 123 321.