Problem description

-Ten świat jest padołem łez, Greg. Życie to nie zabawa. - Beatrice, niebieski ptak, spojrzała z góry na Grega, który niósł swoją żabkę pod pachą. Jej głos był pełen pouczenia i troski. Po kilku minutach jej monologu… Greg już zniknął. - Hej, gdzie jest Greg?

-Och. Uh, pewnie gdzieś sobie poszedł – odparł spokojnie Wirt, poprawiając kapelusz.

Tymczasem Greg biegł przez las z dzbankiem i żabką na głowie, z energią, która mogłaby zawstydzić wiatr.

-Musimy robić swoje, aby ten świat był lepszy! - krzyczał, przeskakując przez korzenie.

-Raur – odpowiedziała mu żabka.

Greg zatrzymał się, gdy usłyszał cichą melodię pianina, dobiegającą z budynku pośród drzew.

-Jeju! Szkoła?! Tylko nie dzisiaj! – wrzasnął w panice i uciekł w stronę pobliskiej rzeczki, gdzie zauważył grupę zwierzątek – wagarowiczów, nudzących się w cieniu drzew.

Po krótkiej rozmowie z nowymi towarzyszami, Greg szybko zorientował się, że rozmowa z nimi ma mniej treści, niż rozmowa z dzbanuszkiem na głowie. Żaden z nich nie słyszał o palindromach, nie mówiąc już o kombinatoryce. Greg, nieco zmartwiony, uznał, że świat nie może być tak mdły i nijaki, i postanowił nauczyć swoich nowych znajomych czegoś nowego. Zaczął mówić o swojej ulubionej grze w dwa stare kocury. Ale zaraz przerwał. To nie ta gra. Wrócił więc do sedna i wyjaśnił, że ich zadanie jest proste: wymyślić imię dla jego żabki. Żadnych prostych słów, żadnych banalnych propozycji.

Ale Greg po zrobieniu zadania A, B, i wszystkich pozostałych, nie chciał już stawiać na prostotę. Palindromy w ich klasycznej formie? Nuuuda. Tym razem wpadł na pomysł, by wypróbować formy angażującej wszystkich jego M kolegów do zabawy. Imie dla żabusia powinno być N-literowym słowem, które korzysta z alfabetu o K różnych literach. Każdy z M wagarowiczów wskazuje parę indeksów (l_i,r_i), określając, że podciąg imienia od pozycji l_i do r_i włącznie musi być palindromem.

Dla przypomnienia, palindromem nazywamy słowo, które czytane od lewej do prawej i od prawej do lewej, jest takie samo.

Ale zaraz… - pomyslał Greg. - Ile w ogóle jest takich imion?

Twoim zadaniem jest policzenie, ile różnych imion, spełniających te warunki, Greg może wymyślić dla swojej żabki.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby - N, K oraz M (1 ≤ N, K ≤ 2000, 0 ≤ M ≤ 2000).

W kolejnych M wierszach wejścia znajdują się opisy dane przez kolegów: w i-tym (1 ≤ i ≤ M) wierszu znajduje się para l_i, r_i (1 ≤ l_i ≤ r_i ≤ N).

Wyjście

W jedynym wierszu wyjścia powinna się znaleźć liczba sposobów, na które można stworzyć słowo spełniające warunki Grega, modulo 10⁹ + 7.

Ograniczenia

1 ≤ N, K ≤ 2000,

0 ≤ M ≤ 2000.

Niektóre testy spełniają warunek M = 0.

Przykład

5 3 2
1 3
2 5

9