题目描述

给定一个字符串 $T$，它的长度是 $LT$，那么字符串 $T$ 可以用字符数组 $T[1..LT]$ 来表示。你可以把 $T$ 的任意两个字符交换位置，你可以交换任意多次。经过交换之后的字符串被称为 $T$ 的同构串。

例如: $T=“abac”$,那么 $“aabc”、“aacb”、“baac”、“baca”、“bcaa”、 “caab”、“caba”、“cbaa”$ 等都是字符串T的同构串。而 $“baab”、“bcab”$ 等都不是字符串 $T$的同构串。 再给定一个字符串 $S$ ，长度是 $LS$，那么字符串$S$ 可以用字符数组 $S[1.. LS]$ 来表示。初始时，$ans=0$。对于 $S$ 的任意长度是 $LT$ 的一段(即一个子串)， 如果是字符串 $T$ 的同构串，那么 $ans$ 增加 $1$。你的任务就是输出 $ans$ 最后的值。

输入格式:

第1行，一个字符串T。长度不超过10000，T的每个字符要么是小写字母，要么是大写字母;

第2行，一个字符串S，长度是5000000，S的每个字符要么是小写字母，要么是大写字母。

输出格式:

一个整数，ans最后的值。

样例

aba
baababac

4

样例解释:

当K=1时，S[1..3]=“baa”,是T的同构串。

当K=2时，S[2..4]=“aab”，是T的同构串。

当K=3时，S[3..5]=“aba”，是T的同构串。

当K=4时，S[4..6] =“bab”，不是T的同构串。

当K=5时，S[5..7]=“aba”，是T的同构串。

当K=6时，S[6..8] =“bac”,不是T的同构串。

[数据规模]

对于40%的数据，T的长度不超过100，且S的长度不超过10000。

对于70%的数据，S的长度不超过1000000。

Limitation

1s, 1024KiB for each test case.