E. Гурван тэмдэгт мөр

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

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

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

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

$(s_{1}, s_{2}, s_{3})$ тэмдэгт мөрүүд өгөгдсөн. $l$ $(1 ≤ l ≤ min(|s_{1}|, |s_{2}|, |s_{3}|)$ бүхэл тоо бүрийн хувьд $s_{k}[i_{k}... i_{k} + l - 1]$ $(k = 1, 2, 3)$ тэмдэгт мөрүүд хос хосоороо тэнцүү байдаг ($i_{1}, i_{2}, i_{3}$) гуравтын тоог ол. Олсон нийт боломжийн тоог $1000000007 (10^{9} + 7)$ тоонд хувааж үлдэгдлийг хэвлэ.

Тэмдэглэлээс зарим тэмдэглэгээний тодорхойлолтыг харна уу.

Оролт

Эхний гурван мөрөнд хоосон биш тэмдэгт мөр байрлана. Эдгээр тэмдэгт мөрийн нийт урт $3*10^{5}$-ээс хэтрэхгүй. Бүх тэмдэгт мөр зөвхөн англи жижиг үсгүүдээс бүрднэ.

Гаралт

$min(|s_{1}|, |s_{2}|, |s_{3}|)$ ширхэг хариу болох бүхэл тоог $1000000007 (10^{9} + 7)$ тоонд хуваан үлдэгдлийг зайгаар тусгаарлан хэвлэ.

Орчуулсан: Sugardorj

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

Оролт
abc
bc
cbc
Гаралт
3 1 
Оролт
abacaba
abac
abcd
Гаралт
11 2 0 0 

Тэмдэглэл

$t = t_{1}t_{2}... t_{|t|}$, энд $t_{i}$ нь уг тэмдэгт мөрийн $i$-р үсэг, $|t|$ нь тэмдэгт мөрийн урт.

$t[i... j]$ $(1 ≤ i ≤ j ≤ |t|)$ нь $t_{i}t_{i + 1}... t_{j}$ ($t$-ийн $i$-ээс $j$-р байрлалыг агуулах дэд тэмдэгт мөр) тэмдэгт мөрийг илэрхийлнэ.

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