P9576 "TAOI-2" Ciallo～(∠・ω< )⌒★

Yuzu fans, that is enough. ~(·

Little $\delta$ likes to make up words. He learned a way to make up words. First, he has a "template string", denoted as $s$. Then he chooses a pair $1 \le l \le r \le |s|$, deletes the $l$-th to $r$-th characters of $s$, and concatenates the remaining parts. He denotes the new string obtained as $s'$. Next, he chooses a new pair $1 \le l' \le r' \le |s'|$, and lets $s''$ be the string formed by the $l'$-th to $r'$-th characters of $s'$. The word he makes is $s''$. For example, if the "template string" is $s=\texttt{cciaohalloo}$, then one way is to choose $l=5$, $r=7$, obtaining $s'=\texttt{ccialloo}$, then choose $l'=2$, $r'=7$, obtaining $s''=\texttt{ciallo}$. Now little $\delta$ has a "target string" $t$. He wants to know how many different plans can use the "template string" $s$ to produce the word $t$. Two plans are defined to be the same if and only if the chosen $l,r,l',r'$ are all the same.

There are two lines, which are the strings $s$ and $t$, respectively.

There is one line, representing the number of plans to produce the "target string" $t$.

### Constraints **This problem uses bundled testdata**. - Subtask 0 (6 points): $|s| \le 400$, $|t| \le 200$. - Subtask 1 (10 points): $|s| \le 700$, $|t| \le 300$. - Subtask 2 (10 points): $\forall i,j,s_i=t_j$. - Subtask 3 (10 points): $|t|=1$. - Subtask 4 (20 points): $|s| \le 10^4$, $|t| \le 3 \times 10^3$. - Subtask 5 (14 points): $|t|=2$. - Subtask 6 (30 points): No special constraints. For all testdata, $1 \le |s| \le 4 \times 10^5$, $1 \le |t| \le 2 \times 10^5$. $s,t$ contain only lowercase English letters. Translated by ChatGPT 5