Kopiowanie tandemowe to operacja na DNA, w której powtarza się ciąg jednego lub więcej kolejnych nukleotydów, a powtórzenia są bezpośrednio obok siebie. Innymi słowy, kopiuje się spójny fragment nukleotydów i wkleja kopię tuż za nim. Na przykład skopiowanie $\mathrm{ATC}$ w $\mathrm{ATCG}$ daje $\mathrm{ATCATCG}$. Kolejne kopiowanie w otrzymanym ciągu może dać $\mathrm{ATCATTCG}$. Poniższy przykład pokazuje serię kopii z $\mathrm{ATCG}$; w każdym kroku kopiowany jest podkreślony fragment.

$$\underline{\mathrm{ATC}}\mathrm G\Rightarrow\mathrm{ATCA}\underline{\mathrm T}\mathrm{CG}\Rightarrow\underline{\mathrm{AT}}\mathrm{CATTCG}\Rightarrow\mathrm{ATATC}\underline{\mathrm{ATT}}\mathrm{CG}\Rightarrow\cdots$$

Mówimy, że $\mathrm{ATCG}$ wytwarza wszystkie te ciągi przez kopiowanie tandemowe. Łatwo zauważyć, że wybór innego fragmentu w każdym kroku pozwala wytwarzać różne ciągi. Ponadto, kontynuując kopiowanie tyle razy, ile potrzeba, $\mathrm{ATCG}$ może zasadniczo wytworzyć nieskończenie wiele ciągów.

Zwykle kopiowanie dłuższego fragmentu jest droższe. Na przykład $\underline{\mathrm{ATC}}\mathrm G\Rightarrow\mathrm{ATCATCG}$ kopiuje trzy nukleotydy i jest zatem droższe niż $\mathrm{ATCA}\underline{\mathrm T}\mathrm{CG}\Rightarrow\mathrm{ATCATTCG}$, które kopiuje jeden nukleotyd. Innymi słowy, długość kopiowanego fragmentu w każdym kroku ma kluczowe znaczenie dla kosztu.

Ponieważ łatwo skopiować pojedynczy nukleotyd, laboratorium ICPC wygodnie jest przechowywać ciągi, w których kolejne nukleotydy zawsze są różne; oszczędza to miejsce. Na przykład $\mathrm{ATTTG}$ można uzyskać z $\mathrm{ATG}$, dwukrotnie kopiując $\mathrm T$, więc lepiej przechowywać tylko krótszy ciąg $\mathrm{ATG}$ zamiast $\mathrm{ATTTG}$.

Z powodu niedawnego cięcia budżetu laboratorium ICPC może jednorazowo kopiować tandemowo co najwyżej dwa nukleotydy; kopiowany fragment ma więc w każdym kroku długość co najwyżej dwa. Może natomiast powtarzać operację dowolnie wiele razy. Na przykład dla $\mathrm{ABCD}$ skopiowanie $\mathrm B$ daje $\mathrm{ABBCD}$, a skopiowanie $\mathrm{BC}$ daje $\mathrm{ABCBCD}$. Nie można jednak skopiować spójnego fragmentu $\mathrm{ABC}$, bo jest dłuższy niż dwa.

Dany jest ciąg źródłowy $s$ i docelowy $t$. Policz wszystkie poprawne podciągi spójne $s\prime$ ciągu $s$, z których odpowiednia liczba kopii tandemowych może utworzyć ciąg $x$ zawierający $t$ jako podciąg spójny. Żadne dwa kolejne nukleotydy w ciągu źródłowym nie są takie same, ale w docelowym mogą być. Na przykład $\mathrm{CCA}$ i $\mathrm{ATTGC}$ nie mogą być ciągami źródłowymi, ale mogą być docelowymi.

Dla $s=\mathrm{ACATGCAT}$ i $t=\mathrm{CCACATTT}$ wybieramy podciąg spójny $s\prime=\mathrm{CATGC}$ ciągu $s$ i wykonujemy następującą serię kopii:

$$s\prime=\underline{\mathrm C}\mathrm{ATGC}\Rightarrow\mathrm C\underline{\mathrm{CA}}\mathrm{TGC}\Rightarrow\mathrm{CCACA}\underline{\mathrm T}\mathrm{GC}\Rightarrow\mathrm{CCACAT}\underline{\mathrm T}\mathrm{GC}\Rightarrow\mathrm{CCACATTTGC}$$

Otrzymany ciąg zawiera $t$ jako podciąg spójny.

Oto inny przykład podciągu spójnego. Dla $s\prime=\mathrm{CAT}$:

$$s\prime=\underline{\mathrm{CA}}\mathrm T\Rightarrow\underline{\mathrm C}\mathrm{ACAT}\Rightarrow\mathrm{CCACA}\underline{\mathrm T}\Rightarrow\mathrm{CCACAT}\underline{\mathrm T}\Rightarrow\mathrm{CCACATTT}=t$$

Pokazuje to, że z $\mathrm{CAT}$ można wytworzyć ciąg docelowy przez serię kopii tandemowych.

Łatwo sprawdzić, że łączna liczba poprawnych podciągów spójnych $s$ wynosi $14$. Pierwsze i drugie wystąpienie $\mathrm{CAT}$ w $s$ są liczone jako różne poprawne podciągi spójne. Należy więc rozważyć wszystkie podciągi spójne $s$ i liczyć każdy poprawny oddzielnie.

Oto kolejny przykład. Dla $s=\mathrm{AB}$ i $t=\mathrm{BA}$ można wybrać podciąg spójny $\mathrm{AB}$ i skopiować $\mathrm{AB}$. Wynik $\mathrm{ABAB}$ zawiera $\mathrm{BA}$ jako podciąg spójny. Żaden inny podciąg spójny $s$ nie może wytworzyć $\mathrm{BA}$ jako podciągu spójnego, więc liczba poprawnych wynosi jeden.

Mając ciąg źródłowy $s$, w którym żadne dwa kolejne znaki nie są takie same, i ciąg docelowy $t$, napisz program wypisujący liczbę poprawnych podciągów spójnych $s\prime$ ciągu $s$. Podciąg $s\prime$ jest poprawny, jeśli seria kopii tandemowych może wytworzyć ciąg zawierający $t$ jako podciąg spójny; w każdym kroku wolno skopiować co najwyżej dwa kolejne znaki.

Wejście

Program czyta ze standardowego wejścia. Wejście ma dwa wiersze: pierwszy to ciąg źródłowy $s$, a drugi to docelowy $t$. Każdy składa się z wielkich liter od A do Z i zachodzi $1\le |s|,|t|\le 2\times 10^4$.

Wyjście

Program pisze na standardowe wyjście. Wypisz dokładnie jeden wiersz zawierający liczbę poprawnych podciągów spójnych, z których seria kopii tandemowych może wytworzyć ciąg zawierający ciąg docelowy jako podciąg spójny.

Poniżej pokazano przykładowe wejście i wyjście dla czterech przypadków testowych.

Przykład

Wejście 1

ACGCG
CCG

Wyjście 1

9

Wejście 2

TATCGC
TTCCG

Wyjście 2

6

Wejście 3

ABCABC
ABC

Wyjście 3

7

Wejście 4

ABCABC
ABCABC

Wyjście 4

1