Susan dobrze radzi sobie z wygodnym ustawianiem rzeczy na stole w jadalni, ale nie na biurku w pracy.

Susan właśnie skończyła pracę nad zestawem dokumentów, które wciąż leżą w stosie na jej biurku. Mają numery porządkowe i były ułożone w kolejności, gdy przyniósł je szef. Teraz kolejność nie jest jednak idealna, ponieważ Susan nie chciało się odkładać dokumentów wyjętych ze stosu na właściwe miejsca. Dowiedziawszy się, że skończyła, szef chce, aby natychmiast zwróciła dokumenty w pudełku, które jej wysyła. Oczywiście dokumenty powinny zostać umieszczone w pudełku w kolejności numerów.

Na biurku jest miejsce na dokładnie dwa dodatkowe stosy dokumentów, więc Susan planuje utworzyć tam dwa tymczasowe stosy. Wszystkie dokumenty z obecnego stosu należy przenieść, po jednym z góry, na jeden z dwóch tymczasowych stosów. Ponieważ stosy układane pospiesznie zbyt wysoko mogłyby się przewrócić, nie wolno umieszczać na nich zbyt wielu dokumentów. Po przeniesieniu wszystkich dokumentów na tymczasowe stosy i otrzymaniu pudełka dokumenty zostaną przeniesione z ich wierzchołków, po jednym, do pudełka. Na obu stosach dokumenty powinny być ułożone w odwrotnej kolejności numerów, aby można je było przenosić do pudełka w kolejności.

Na przykład załóżmy, że stos zawiera sześć dokumentów o numerach $1,3,4,2,6,5$, w tej kolejności od góry, a tymczasowe stosy mogą zawierać najwyżej trzy dokumenty. Susan może utworzyć stos z dokumentami $6,4,3$ od góry i drugi z $5,2,1$ (patrz ilustracja). Oba są uporządkowane w odwrotnej kolejności. Następnie porównuje numery dokumentów na wierzchołkach obu stosów; dokument o większym numerze (w tym przypadku $6$) należy wyjąć i jako pierwszy włożyć do pudełka. Powtarzając to, wszystkie dokumenty zostaną idealnie uporządkowane w pudełku.

Susan zastanawia się, czy plan jest wykonalny dla dokumentów w obecnym stosie, a jeśli tak, na ile różnych sposobów można ułożyć je na dwóch tymczasowych stosach. Pomóż jej, pisząc program obliczający tę liczbę sposobów, która powinna wynosić zero, jeśli plan jest niewykonalny.

Ponieważ każdy dokument można przenieść na dowolny z dwóch tymczasowych stosów, dla $n$ dokumentów istnieje łącznie $2^n$ kombinacji wyborów. Niektóre mogą jednak naruszyć odwrotną kolejność na tymczasowych stosach, więc są niewłaściwe.

Opisany przykład odpowiada pierwszemu przypadkowi w przykładowym wejściu. W tym przypadku można zamienić miejsca docelowe ostatnich dwóch dokumentów, $5$ i $6$. Można też całkowicie zamienić role dwóch tymczasowych stosów. Ponieważ każda inna sekwencja ruchów spowodowałaby, że jeden stos miałby więcej niż trzy dokumenty lub dokumenty byłyby w niewłaściwej kolejności, łączna liczba sposobów ułożenia dokumentów na tymczasowych stosach w tym przykładzie wynosi $2\times2=4$.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n,m$. $n$ jest liczbą dokumentów w stosie ($1\le n\le5000$), a $m$ liczbą dokumentów, które można umieścić na jednym tymczasowym stosie bez ryzyka przewrócenia ($n/2\le m\le n$). Następny wiersz zawiera liczby od $s_1$ do $s_n$, będące numerami dokumentów w stosie w kolejności od góry do dołu. Gwarantuje się, że wszystkie liczby od $1$ do $n$ występują dokładnie raz.

Wyjście

Wypisz w jednym wierszu jedną liczbę całkowitą oznaczającą liczbę sposobów utworzenia dwóch tymczasowych stosów odpowiednich do celu.

Jeśli żaden wybór nie działa, liczba sposobów wynosi oczywiście $0$. Jeśli liczba możliwych sposobów jest większa lub równa $10^9+7$, wypisz ją modulo $10^9+7$.

Przykład

Wejście 1

6 3
1 3 4 2 6 5

Wyjście 1

4

Wejście 2

6 6
1 3 4 2 6 5

Wyjście 2

8

Wejście 3

4 4
4 3 1 2

Wyjście 3

0