C. Левко ба тэмдэгт мөр

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

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

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

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

Левкод Англи цагаан толгойн жижиг үсгээс бүтсэн $n$ урттай тэмдэгт мөр таалагддаг.Түүнд ийм $s$ тэмдэгт мөр байгаа. $n$ урттай $t$ тэмдэгт мөрийн хувьд Левко түүний $s$-тэй харьцангуй үзэмжийг дараах нөхцөлийг хангах $i, j (1\le i\le j\le n)$ хосын тоогоор тодорхойлдог: $t[i..j]$ дэд тэмдэгт мөр нь лексикограф эрэмбэлэлээр $s[i..j]$ дэд тэмдэгт мөрөөс их.

Левко хүү $s$-тэй харьцангуй үзэмж нь $k$ байдаг хэдэн $t$ тэмдэгт мөр байгааг мэдэхийг хүсчээ. Түүнд тусалж түүний мэдэхийг хүсч буй тоог 1000000007 тоонд хуваахад гарах үлдэгдлийг олно уу.

$s=s_1s_2... s_n$-н $s[i..j]$ дэд тэмдэгт мөр гэдэг нь $s_is_{i+1}... s_j$ юм6

$x=x_1x_2... x_p$ , $y  =  y_1y_2... y_p$ тэмдэгт мөрүүдийн хувьд $x_1=y_1,x_2=y_2,... ,x_r=y_r , x_{r+1}>y_{r+1}$ байх $r (r

Оролт

Эхний мөр $n ,k (1\le n\le 2000, 0\le k\le 2000)$ тоонуудыг агуулна.

Удаах мөрөнд $n$ ширхэг Англи цагаан толгойн жижиг үсгүүдээс тогтох $s$. тэмдэгт мөр өгөгдөнө.

Гаралт

Бодлогын хариуг 1000000007 тоонд хуваахад гарах үлдэгдлийг хэвлэ.

Орчуулсан: Төрбат

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

Оролт
2 2
yz
Гаралт
26
Оролт
2 3
yx
Гаралт
2
Оролт
4 7
abcd
Гаралт
21962
Сэтгэгдлүүдийг ачааллаж байна...