Two strings $A$ and $B$ consisting of lowercase English letters are said to be "isomorphic" if the following conditions are satisfied:

1. The lengths of $A$ and $B$ are equal.
2. For all possible integers $i$ and $j$, the $i$-th and $j$-th characters of $A$ are equal if and only if the $i$-th and $j$-th characters of $B$ are equal.
3. For all possible integers $i$ and $j$, the $i$-th and $j$-th characters of $A$ are different if and only if the $i$-th and $j$-th characters of $B$ are different.

For example, $A = \text{aba}$ and $B = \text{pqp}$ are isomorphic strings. However, $A = \text{abca}$ and $B = \text{abcb}$ are not a pair of isomorphic strings.

Write a program that takes strings $T$ and $P$ and calculates the number of contiguous substrings of $T$ that are isomorphic to $P$.

For example, if $T = \text{abababbab}$ and $P = \text{pqp}$, we can see that the 5 substrings of $T$ starting from the left, which are $\text{aba}$, $\text{bab}$, $\text{aba}$, $\text{bab}$, and $\text{bab}$, are isomorphic to $P$.

You must implement the following function:

• int findP(char T[], char P[], int N, int M): $T$ is an array (string) of length $N+1$. $P$ is an array of length $M+1$. $T$ and $P$ contain lowercase English strings of length $N$ and $M$, respectively. The last position of $T$ and $P$ stores '\0'. findP should return the number of contiguous substrings of $T$ that are isomorphic to $P$.

Implementation Details

You must submit exactly one file named match.cpp. This file must implement the following function:

• int findP(char T[], char P[], int N, int M)

This function must behave as described above. You may implement other functions to use internally. The submitted code must not perform I/O or access other files.

Constraints

• $1 \le N \le 1,000,000$, $1 \le M \le N$.

Subtasks

• Subtask 1 [8 points]: $N = M$
• Subtask 2 [5 points]: $1 \le N \le 100$
• Subtask 3 [12 points]: $1 \le N \le 2,000$
• Subtask 4 [75 points]: No additional constraints other than the original constraints.

Examples

Input 1

abababbab
pqp

Output 1

5

Note

The following table shows an example of how your code operates based on the input above.