D. Тавас Малекас хоёр

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

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

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

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

Тавас их хачин амьтан юм. Хүмүүс унтаж байхад амнаас нь ихэвчлэн "zzz" гардаг бол Тавасын амнаас $n$ урттай $s$ тэмдэгт мөр гардаг.

Өнөөдөр Тавас Малекасынд унтаж байна. Түүнийг унтаж байх хооронд Малекас $s$ тэмдэгт мөр дээр бяцхан үйлдэл хийжээ. Малекас $p$ тэмдэгт мөрд дуртай. Тэр $p$-н $s$-тэй тохирч байгаа бүх $x_{1} < x_{2} < ... < x_{k}$ байрлалуудыг тодорхойлжээ. Томъёолбол: $x_{i}$ ($1 ≤ i ≤ k$) бүрийн хувьд $s_{x_{i}}s_{x_{i} + 1}... s_{x_{i} + |p| - 1} = p$ тэнцэтгэлийг хангана.

Дараа нь Малекас $x_{1}, x_{2}, ... x_{k}$ (юу ч бичээгүй байж болно) дэд дарааллуудын нэгийг нь цаасан дээр бичжээ. Хэрвээ $a$ дарааллын зарим элементийг устгах (ямар ч элемент устгахгүй байж болно эсвэл бүх элементийг устгаж ч болно) замаар $b$ дараалал руу хувиргаж болж байвал $b$ дарааллыг $a$ дарааллын дэд дараалал гэнэ.

Тавасыг сэрсний дараа Малек түүнд бүхнийг хэлэв. Тэр $s$ тэмдэгт мөрийг санахгүй байгаа ч $s$, $p$ тэмдэгт мөрүүд хоёулаа Англи жижиг үсэгнээс бүрддэг гэдгийг мэдэж байгаа. Мөн түүнд цаасан дээр бичсэн дэд дараалал байгаа.

$s$ тэмдэгт мөрийн боломжит утгуудын тоо хэд байх бол? гэж Тавас бодов. Тэр Саддасаас асуусан боловч Саддас асуултанд хариулж чадахаар хангалттай ухаалаг биш байлаа. Тиймээс Тавас энэ тоог олохыг танаас хүсэж байна.

Хариулт хэтэрхий том тоо байж болох учраас хариуг $10^{9} + 7$-д хуваагаад гарсан үлдэгдлийг хэвлэнэ үү.

Оролт

Эхний мөрөнд $n$, $m$ бүхэл тоонууд байна. Эдгээр нь $s$ тэмдэгт мөрийн урт болон Малекын бичсэн дэд дарааллын урт юм ($1 ≤ n ≤ 10^{6}; 0 ≤ m ≤ n - |p| + 1$).

Хоёр дахь мөрөнд $p$ ($1 ≤ |p| ≤ n$) тэмдэгт мөр байна.

Дараагийн мөрөнд $m$ ширхэг зайгаар тусгаарлагдсан $y_{1}, y_{2}, ..., y_{m}$ бүхэл тоонууд байна. Эдгээр нь Малекын дэд дараалал юм ($1 ≤ y_{1} < y_{2} < ... < y_{m} ≤ n - |p| + 1$).

Гаралт

Хариуг $1000000007$-д хуваагаад гарсан үлдэгдлийг хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
6 2
ioi
1 3
Гаралт
26
Оролт
5 2
ioi
1 2
Гаралт
0

Тэмдэглэл

Эхний жишээнд "ioioi?" хэлбэрийн тэмдэгт мөрийн асуултын тэмдгийн оронд дурын (бүх) Англи үсэг тохирно.

Тохирох тэмдэгт мөр байхгүй байж болно гэдгийг анхаараарай. (Ийм тохиолдолд хариулт нь "0" байна).

Сэтгэгдлүүдийг ачааллаж байна...