B. Бодлоос гардаггүй тэмдэгт мөр

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

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

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

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

Хэмид саяхан $t$ тэмдэгт мөр олсон бөгөөд түүнд энэ тэмдэгт мөр тун их таалагджээ. Тэгээд тэр өөрт байсан бусад тэмдэгт мөрүүдэд энэхүү $t$ тэмдэгт мөр агуулагдаж байсан эсэхийг мэдэх гэж хэдэн өдөр зарцуулсан байна. Эцэст нь тэр нэлээд залхах аястай болсон тул дараах бодлогын талаар бодож эхэлжээ:

"Өгөгдсөн $s$ тэмдэгт мөрөөс $t$ тэмдэгт мөрийг агуулсан $k ≥ 1$ байх хоорондоо огтлолцохгүй дэд тэмдэгт мөрүүд гаргаж авах хэдэн арга байгаа вэ?"

Томъёолбол дараах нөхцлүүдийг хангасан $a_{1}, a_{2}, ..., a_{k}$ ба $b_{1}, b_{2}, ..., b_{k}$ хоёр дарааллыг сонгох хэдэн арга байгааг тооцоолох юм:

  • $k ≥ 1$
  • $∀i\ (1 ≤ i ≤ k)$ $1 ≤ a_{i},b_{i} ≤ |s|$
  • $∀i\ (1 ≤ i ≤ k)$ $b_{i}≥a_{i}$
  • $∀i\ (2 ≤ i ≤ k)$ $a_{i}>b_{i-1}$
  • $∀i\ (1 ≤ i ≤ k)$ $t$ нь $s_{a_{i}}s_{a_{i} + 1}... s_{b_{i}}$ тэмдэгт мөрийн дэд тэмдэгт мөр байна ($s$ тэмдэгт мөрийг $1$-с эхлэн дугаарлагдсан гэж үзнэ).

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

Оролт

Оролтын эхний мөр нь $s$ тэмдэгт мөрийг, хоёр дахь мөр нь $t$ ($1 ≤ |s|, |t| ≤ 10^{5}$) тэмдэгт мөрийг агуулна. Тэмдэгт мөр бүр нь Латин жижиг үсгээс бүрдэнэ.

Гаралт

Хариуг нэг мөрөнд хэвлэнэ.

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

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

Оролт
ababa
aba
Гаралт
5
Оролт
welcometoroundtwohundredandeightytwo
d
Гаралт
274201
Оролт
ddd
d
Гаралт
12
Сэтгэгдлүүдийг ачааллаж байна...