Problem Description

Little M has decided to start writing a diary, but she doesn't want to spend too much time thinking about its content. For this reason, she has found a string \( S \) of length \( n \) and decided to randomly select a prefix \( P \) of \( S \) and a suffix \( Q \) of \( S \), then concatenate \( P \) and \( Q \) to form the string \( P+Q \) as the content of her diary. Here, the empty string is also considered a prefix and suffix of \( S \), so there are \( n+1 \) ways to choose \( P \) and \( Q \).

Of course, many of the strings formed in this way are meaningless. Specifically, Little M considers a known string \( T \) of length \( m \) to be important information, and any string containing this important information as a substring is meaningful, otherwise it is meaningless.

Please calculate how many distinct meaningful strings Little M can write. Distinct means that for a meaningful string \( A \), even if it can be obtained in several ways by choosing prefixes and suffixes, it should only be counted once.

Input Format

The input consists of two lines.

The first line contains a string \( S \).

The second line contains a string \( T \).

Output Format

Output a single integer, the answer to the problem.

Sample Input and Output

Sample Input #1

aab
ab

Sample Output #1

7

Sample Input #2

mikageandspica
spica

Sample Output #2

140

Sample Input #3

See the files in the选手目录下的 diary/diary3.in and diary/diary3.ans.

Sample Output #3

See the files in the选手目录下的 diary/diary3.in and diary/diary3.ans.

Sample Input #4

See the files in the选手目录下的 diary/diary4.in and diary/diary4.ans.

Sample Output #4

See the files in the选手目录下的 diary/diary4.in and diary/diary4.ans.

Sample Input #5

See the files in the选手目录下的 diary/diary5.in and diary/diary5.ans.

Sample Output #5

See the files in the选手目录下的 diary/diary5.in and diary/diary5.ans.

Notes

Sample 1 Explanation

For the first sample, all meaningful strings that can be formed are ab, aab, aaab, aaaab, aabaab, aabab, aabb, totaling 7.

Subtasks

For all test data, it is guaranteed that \( 1 \leq |S| \leq 5 \times 10^6 \), \( 1 \leq |T| \leq 2|S| \), and the input strings \( S \) and \( T \) contain only lowercase English letters. Here, \( |S| \) and \( |T| \) denote the lengths of strings \( S \) and \( T \), respectively.

• August 21, 2023: Added a set of hack data.

见题面 Input 部分

见题面 Output 部分