E. Сул дэд дараалал

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

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

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

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

Бяцхан Петя тэмдэгт мөрүүдэд үнэхээр их дуртай. Саяхан тэрээр ээжээсээ бэлэг болгон тэмдэгт мөр худалдан авах эрхийн бичиг авчээ. Тэмдэгт мөрийг орон нутгийн дэлгүүрээс авч болно. Дэлгүүр нь тогтмол хэмжээтэй (ашиглаж болох үсгийн тоо нь тогтмол) цагаан толгойн бүх төрлийн тэмдэгт мөрүүдийг зардаг гэж үзэх юм. Цагаан толгойн үсгийн тоо нь $k$-тай тэнцүү. Тэгсэн хэдий ч эрхийн бичиг нь худалдан авах тэмдэгт мөрийн төрлийн хязгаартай: ялангуяа, хэрэв тэмдэгт мөрийн хамгийн урт дэд тэмдэгт мөрийн урт, мөн энэ нь уг тэмдэгт мөрийн сул дэд дараалалын (доорх тодорхойлолтыг харна уу) урт нь $w$-тай тэнцүү байвал эрхийн бичгээр уг $s$ тэмдэгт мөрийг худалдан авч болно.

Хэрэв дараах 2 нөхцөлийг хангах $1 ≤ i_{1} < i_{2} < ... < i_{n} ≤ m$ индексүүдийн олонлог оршин байвал $n$ урттай $a$ тэмдэгт мөрийг $m$ урттай $s$ тэмдэгт мөрийн сул дэд дараалал гэж үзнэ:

  • $1$-ээс $n$ хүртэлх бүх $k$-ын хувьд $a_{k} = s_{i_{k}}$;
  • $i_{k + 1} - i_{k} > 1$ байх дор хаяж нэг ширхэг $k$ ($1 ≤ k < n$) оршин байна.

Петя түүнд дэлгүүрээс худалдан авах боломжтой хэчнээн ширхэг ялгаатай тэмдэгт мөрүүд байгааг сонирхжээ. Уг тоо нь хэтэрхий том байж болох учраас, уг тоог $1000000007$ ($10^{9} + 7$) модулаар бодож олно уу. Хэрэв ийм тэмдэгт мөрүүд хязгааргүй олон байвал, "-1" гэж хэвлэнэ үү.

Оролт

Эхний мөрөнд 2 бүхэл тоо $k$ ($1 ≤ k ≤ 10^{6}$) болон $w$ ($2 ≤ w ≤ 10^{9}$) өгөгдөнө -- эдгээр нь харгалзан цагаан толгойн хэмжээ болон хамгийн урт дэд тэмдэгт мөр буюу сул дэд дарааллын шаардагдсан уртыг илэрхийлнэ.

Гаралт

Ганц тоо хэвлэнэ -- энэ нь Петя эрхийн бичгээр худалдан авч болох тэмдэгт мөрийн тоог $1000000007$ ($10^{9} + 7$) модулаар бодсон утга байна. Хэрэв ийм тэмдэгт мөрүүд хязгааргүй олон байвал, "-1" (хашилтгүйгээр) гэж хэвлэнэ үү.

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

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

Оролт
2 2
Гаралт
10
Оролт
3 5
Гаралт
1593
Оролт
2 139
Гаралт
717248223

Тэмдэглэл

Эхний жишээнд Петя дараах тэмдэгт мөрүүдийг худалдан авч болно: aaa, aab, abab, abb, abba, baa, baab, baba, bba, bbb.

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