Нэг өдөр Поликарпус Латин жижиг үсгээс бүрдсэн хоосон биш хоёр тэмдэгт мөр $s$ болон $t$-тэй болсон. Поликарпус тэмдэгт мөрүүдтэй сайн ажилладаг ба тэр шууд $x$ нь $s$ тэмдэгт мөрийн дэд тэмдэгт мөр харин $y$ нь $t$ тэмдэгт мөрийн дэд дараалал байх ба $x$, $y$ нь ижилхэн агуулгатай байх хичнээн ялгаатай "$x$ $y$" хос байх вэ гэж гайхсан. Хэрвээ хоёр хос нь $s$-н ялгаатай дэд тэмдэгт мөрүүд эсвэл $t$-н ялгаатай дэд дарааллуудыг агуулсан байвал ялгаатайд тооцогдоно. Ялгаатай дэд тэмдэгт мөрүүд ба ялгаатай дэд дарааллуудын тайлбарыг ойлгохын тулд нөхцлийг бүхэлд нь уншина уу.

$s$ тэмдэгт мөрийн урт нь түүнд байгаа үсгүүдийн нийлбэр байна. Хэрвээ бид $s$ тэмдэгт мөрийн уртыг $|s|$ гэж тэмдэглэвэл энэ тэмдэгт мөрийг $s = s_{1}s_{2}... s_{|s|}$ гэж бичиж чадна.

$s$-н дэд тэмдэгт мөр нь $x = s[a... b] = s_{a}s_{a + 1}... s_{b}$ ($1 ≤ a ≤ b ≤ |s|$) тэмдэгт мөр байна. Жишээлбэл "$code$" болон "$force$" нь "$codeforces$" тэмдэгт мөрийн дэд тэмдэгт мөрүүд байхад "$coders$" биш байна. Хэрвээ $a ≠ c$ эсвэл $b ≠ d$ байвал $s[a... b]$ болон $s[c... d]$ тэмдэгт мөрүүд нь ялгаатайд тооцогдоно. Жишээлбэл хэрвээ $s$="$codeforces$" бол $s[2...2]$ ба $s[6...6]$ нь ижил агуулгатай боловч ялгаатайд тооцогдоно.

$s$-н дэд дараалал нь $y = s[p_{1}p_{2}... p_{|y|}] = s_{p_{1}}s_{p_{2}}... s_{p_{|y|}}$ ($1 ≤ p_{1} < p_{2} < ... < p_{|y|} ≤ |s|$) байна. Жишээлбэл "$coders$" бол "$codeforces$"-н дэд дараалал. Дарааллуудын $p$ ба $q$ нь ялгаатай байвал $u = s[p_{1}p_{2}... p_{|u|}]$ болон $v = s[q_{1}q_{2}... q_{|v|}]$ дэд дарааллууд ялгаатайд тооцогдоно.

Оролт

Оролт хоёр мөрөөс тогтоно. Эхний мөрөнд $s$ ($1 ≤ |s| ≤ 5000$) байх ба хоёр дахь мөрөнд $t$ ($1 ≤ |t| ≤ 5000$) байна. Хоёр тэмдэгт мөр хоёулаа Латин жижиг үсгээс тогтоно.

Гаралт

$x$ нь $s$ тэмдэгт мөрийн дэд тэмдэгт мөр харин $y$ нь $t$ тэмдэгт мөрийн дэд дараалал байх ба $x$, $y$ нь ижилхэн агуулгатай байх ялгаатай "$x$ $y$" хосуудын тоог илэрхийлэх нэг бүхэл тоон утгыг хэвлэ. Хариулт маш их байж болох учир $1000000007$ $(10^{9} + 7)$ тоонд хуваагаад үлдэгдлийг хэвлэ.

Эхний жишээний хариултыг бүрдүүлэх бүх "$x$ $y$" хосуудыг цувуулан бичье: "$s[1...1]$ $t[1]$", "$s[2...2]$ $t[1]$", "$s[1...1]$ $t[2]$","$s[2...2]$ $t[2]$", "$s[1...2]$ $t[1 2]$".