Counting Permutations with Substring

Given a string n and a substring h, count the number of distinct permutations of n that contain h as a contiguous substring.

Note: The string n can contain duplicate characters.

Mathematical formulation:

Let \(P(n)\) be the set of distinct permutations of the characters of \(n\). You need to compute the number of \(p \in P(n)\) such that \(h\) is a substring of \(p\). All formulas and explanations are given in \(\LaTeX\) format.

inputFormat

The input consists of two lines:

• The first line contains the string \(n\).
• The second line contains the substring \(h\).

outputFormat

Output a single integer representing the number of distinct permutations of \(n\) in which \(h\) appears as a substring.

sample

ab
a

2