Word Formation Count

Little δ loves coining new words. He learned a method of creating words as follows:

Given a template string \( s \), he performs two operations:

1. Choose a pair of indices \( (l, r) \) with \( 1 \le l \le r \le |s| \) and remove the characters from the \( l \)-th to the \( r \)-th positions of \( s \). The remaining parts are concatenated to form a new string \( s' \).
2. Choose a pair of indices \( (l', r') \) with \( 1 \le l' \le r' \le |s'| \) and extract the substring from the \( l' \)-th to the \( r' \)-th positions of \( s' \) to obtain \( s'' \).

Given a target string \( t \), determine the number of distinct quadruples \( (l, r, l', r') \) such that \( s'' = t \). Two quadruples are considered identical only if all four chosen indices are the same.

inputFormat

The input consists of two lines:

1. The first line contains the template string \( s \).
2. The second line contains the target string \( t \).

Both strings consist of printable characters.

outputFormat

Output a single integer representing the number of distinct quadruples \( (l, r, l', r') \) that can generate \( t \) from \( s \) through the described process.

sample

cciaohalloo
ciallo

1