Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: genome.in

Rezultatų failas: genome.out

Jei norite pateikti savo sprendimą - prisijunkite.

Genai

Bet kurio marsiečio DNR yra sudarytas iš ne daugiau kaip m nukleotidų, sunumeruotų nuo 1 iki m. Kai kurios poros nukleotidų negali eiti iš eilės. Pavyzdžiui, jei marsiečio DNR negali turėti iš eilės einančio nukleotido 1 ir nukleotido 2, tai [1,2] yra negalima marsiečio DNR, bet [2,1] gali būti Marsiečio DNR (jei nėra atitinkamo apribojimo). k yra skaičius nukleoditų porų, kurios negali eiti iš eilės marsiečio DNR. Užduotis yra suskaičiuoti, kiek yra ilgio n įmanomų marsiečio DNR sekų.

Pradiniai duomenys

Pirmoje eilutėje yra DNR ilgis n (1\\leqn\\leq10^{15}), skirtingų nukleotidų kiekis m (1\\leqm\\leq52) ir uždraustų porų kiekis k (1\\leqk\\leqm^2). Sekančiose k eilučių yra po du skaičius a_i,b_i (1\\leqa_i,b_i\\leqm). a_i ir b_i negali eiti šita tvarka iš eilės marsiečio DNR grandinėje. Visos pateiktos poros yra skirtingos, t.y. a_i\\neqa_j,b_i\\neqb_j kai i\\neqj.

Rezultatai

Tegu N yra leidžiamų n ilgio marsiečio DNR grandinių kiekis. Išveskite liekaną N dalijant iš 1000000007 (10^9+7).

Pavyzdys

Duomenys Rezultatai 
3 3 1
2 2
 
22
 
5 3 2
3 1
1 1
 
99