题目描述

小s同学最近对字符串有了浓厚的兴趣，他把符合如下规则的字符串称成为亲戚字符串，简称亲戚串；例如: 字符串 $s = “abac”$,那么 $“aabc”、“aacb”、“baac”、“baca”、“bcaa”、 “caab”、“caba”、“cbaa”$ 等都是字符串 $s$ 的亲戚串。而 $“baab”、“bcab”$ 等都不是字符串 $s$ 的亲戚串；即可以把 $s$ 的任意多个字符交换位置，也可以交换任意多次。经过交换之后的字符串被称为 $s$ 的亲戚串。

给定另一由大小字母组成的字符串 $str$,求出其子串中是字符串 $s$的亲戚串数量。

输入格式:

第 $1$ 行，一个字符串 $s$。长度不超过$10,000$;

第 $2$ 行，另一个字符串 $str$，长度不超过$1000,000$，但大于 $s$ 的长度。

输出格式:

字符串 $str$,子串中是字符串 $s$的亲戚串数量。

样例

aba
baababac

4

[数据规模]

对于$40\%$的数据，$s$ 的长度不超过 $100$，且 $str$ 的长度不超过$10,000$。

对于 $100\%$ 的数据，$str$ 的长度不超过 $1000,000$。

Limitation

1s, 1024KiB for each test case.