E. Сэлгэмлийг эрэмбэлэх

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бидэнд $1$-ээс $n$ хүртэлх бүхэл тоонуудын сэлгэмэл $a_{1}, a_{2}, ..., a_{n}$ өгөгджээ . Бид нэг секундэд давхцаагүй $(u_{1}, v_{1}), (u_{2}, v_{2}), ..., (u_{k}, v_{k})$ хосуудыг сонгон $i$ бүрийн хувьд $a_{u_{i}}$ ба $a_{v_{i}}$-ийн байрыг нэгэн зэрэг сольж чадна ($1 ≤ u_{i} < v_{i} ≤ n$). Бүх $(u_{i}, v_{i})$ хосууд хоорондоо ялгаатай үед давхцаагүй гэж үзнэ.

Бид сэлгэмлийг аль болох хурдан өсөх дараалалтай болгохыг хүсч байгаа. Анхны сэлгэмэл өгөгдсөнөөр хамгийн богино хугацаанд өсөх дарааллаар эрэмбэлэх боломжийн тоог ол. Хоёр боломжийг ямар нэгэн $t$ хугацааны хувьд сонгогдсон хосуудын олонлог ялгаатай үед ялгаатай боломж гэж үзнэ. (Тиймээс сонгосон хосуудад эрэмбэ хамаарахгүй). Хэрэв анхны сэлгэмэл хэдийнээ эрэмбэлэгдсэн бол түүнийг өсөх эрэмбээр эрэмбэлэх боломжийн тоо $1$ гэсэн үг.

Бодлогыг илүү сонирхолтой болгохын тулд сэлгэмэл дотор $k$ нүх оруулжээ. Тиймээс $a_{1}, a_{2}, ..., a_{n}$ нараас яг $k$ ширхэг тоо нь мэдэгдэхгүйгээр өгөгдөх юм. Нүхнүүдийг бөглөх боломж бүрт тухайн сэлгэмлийг хамгийн богино хугацаанд өсөх дараалалд оруулах боломжийн тоог тооцон, тэр бүгдийн нийлбэрийг $1000000007$ $(10^{9} + 7)$ тоонд хуваан үлдэгдлийг хэвлэ.

Оролт

Эхний мөрөнд $n$ $(1 ≤ n ≤ 10^{5})$, $k$ $(0 ≤ k ≤ 12)$ гэсэн хоёр бүхэл тоо байна. Дараагийн мөрөнд $a_{1}, ..., a_{n}$ $(0 ≤ a_{i} ≤ n)$ сэлгэмэл өгөгдөнө. Үл мэдэгдэх тоонууд $0$-ээр тэмдэглэгдэнэ. Өгөгдөлд яг $k$ ширхэг тэг байна. Тэгээс ялгаатай $a_{i}$-үүд хоорондоо ялгаатай байх болно.

Гаралт

Боломжуудын нийлбэрийг $1000000007$ $(10^{9} + 7)$ тоонд хуваан үлдэгдлийг хэвлэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
5 0
1 5 2 4 3
Гаралт
6
Оролт
5 2
1 0 2 4 0
Гаралт
7
Сэтгэгдлүүдийг ачааллаж байна...