E. Оюунлаг судалгаа

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

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

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

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

Цагаан толгой мэдэхгүйгээс болж өөрийнхөө сурвалжлах ажлаасаа халагдсаны дараа,Бэссие Филлет болон Өндөг идэгчдийн коллежид суралцахаар шийджээ.Тэрээр өөрийн сурлагадаа сайн ахицтай байгаа бөгөөд одоо Англи үсгийн эхний $k$ ширхэг үсгийг нь мэддэг болжээ.

Өглөө болгон, Бэссие $m + n$ хавтангаас тогтох явган хүний зам дагуу алхдаг.Бэссие-д хичээлээ давтахад туслах үүднээс, Ноён Мүүзинг явган хүний замын эхний $m$ ширхэг хавтан бүр дээр Англи эхний $k$ ширхэг жижиг үсгийн нэгийг наасан ба нийтдээ тэмдэгт мөр $t$ хэлбэртэй дуудагдана.Ноён Мүүзинг-д Бэссие-ийн өргөн хүрээтэй фермийн амьтдын мэдлэг их сэтгэгдэл төрүүлсэн ба түүнийг өөрөөр нь явган хүний замын сүүлийн $n$ ширхэг хавтанд үсэг наалгахаар төлөвлөжээ.

Үр дүнгийн тэмдэгт мөр $s$ ($|s| = m + n$) нь гэрээс сургууль хүртэлх хавтангууд дээр наасан үсгүүдээс тогтохыг анхаарна уу.Ямар ч индексүүдийн дараалал $p_{1} < p_{2} < ... < p_{q}$-ын хувьд бид $s$ тэмдэгт мөрийн дэд дарааллаар $s_{p_{1}}s_{p_{2}}... s_{p_{q}}$-ын тодорхойлж болох юм.Хэрэв тэмдэгтүүдээрээ ялгаатай байвал уг 2 дэд дарааллыг ялгаатай гэж үзнэ.Бэссие хавтангуудын ялгаатай дэд дарааллуудын тоо нь хамгийн их байхаар явган хүний замын үлдсэн хэсэгт үсэг наахыг хүсэж байгаа юм.Гэсэн хэдий ч, Бэссие цагаан толгойгоо үзэж дуусаагүй байгаа тул түүнд таны тусламж хэрэг болжээ!

Хоосон дэд дарааллууд нь мөн тоологдохыг анхаарна уу.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $k$ ($0 ≤ n ≤ 1 000 000$, $1 ≤ k ≤ 26$) өгөгдөнө.

2-дахь мөрөнд зөвхөн Англи эхний $k$ ширхэг жижиг үсгүүдээс бүрдэх тэмдэгт мөр $t$ ($|t| = m, 1 ≤ m ≤ 1 000 000$) өгөгдөнө.

Гаралт

Бэссие явган хүний замын сүүлийн $n$ ширхэг хавтан болгонд Англи эхний $k$ ширхэг жижиг үсгийн аль нэгийг наасны дараах ялгаатай дэд дарааллуудын хамгийг их тоог тодорхойлно.Уг тоо нь том тоо байх тул та хариултаа $10^{9} + 7$ модулаар бодож хэвлэнэ үү.

Анхаарна уу, та $10^{9} + 7$ модулын үлдэгдлийн утгыг хамгийн их байлгах зорилгогүй! Таны зорилго бол анхны утгыг хамгийн их байлгаад дараа нь уг тооныхоо үлдэгдлийг хэвлэх юм.

Орчуулсан: Баатархүү

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

Оролт
1 3
ac
Гаралт
8
Оролт
0 2
aaba
Гаралт
10

Тэмдэглэл

Эхний жишээнд, оновчтой наалт нь $8$ ширхэг ялгаатай дэд дараалал үүсгэнэ: "" (хоосон тэмдэгт мөр), "$a$", "$c$", "$b$", "$ac$", "$ab$", "$cb$", болон "$acb$".

2-дахь жишээнд, явган хүний зам нь бүхэлдээ наагдсан байна.$10$ ширхэг боломжит ялгаатай дэд дараалал байна:"" (хоосон тэмдэгт мөр), "$a$", "$b$", "$aa$", "$ab$", "$ba$", "$aaa$", "$aab$", "$aba$", болон "$aaba$".Зарим тэмдэгтүүд, жишээ нь "$aa$", нь хавтангуудын олон тооны дараалалд байгаа боловч ганц тоологдож байгааг анхаарна уу.

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