When online chatting, we can save what somebody said to form his ''Classic Quotation''. Little Q does this, too. What's more? He even changes the original words. Formally, we can assume what somebody said as a string $S$ whose length is $n$. He will choose a continuous substring of $S$(or choose nothing), and remove it, then merge the remain parts into a complete one without changing order, marked as $S'$. For example, he might remove ''not'' from the string ''I am not SB.'', so that the new string $S'$ will be ''I am SB.'', which makes it funnier.
After doing lots of such things, Little Q finds out that string $T$ occurs as a continuous substring of $S'$ very often.
Now given strings $S$ and $T$, Little Q has $k$ questions. Each question is, given $L$ and $R$, Little Q will remove a substring so that the remain parts are $S[1..i]$ and $S[j..n]$, what is the expected times that $T$ occurs as a continuous substring of $S'$ if he choose every possible pair of $(i,j)(1\leq i\leq L,R\leq j\leq n)$ equiprobably? Your task is to find the answer $E$, and report $E\times L\times (n-R+1)$ to him.
Note : When counting occurrences, $T$ can overlap with each other.