Palindrome Factory
Consider an arbitrary string (g). We will refer to this string as a palindrome generator. The set of palindromes (P(g)) generated by this string is defined as follows:
Let the length of the string be (n). For each (i) from (1) to (n), the strings (g[1..i]g[1..i]^r) and (g[1..i]g[1..i-1]^r) are included in (P(g)), where (α^r) denotes the reverse of (α).
For example, if (g = "olymp"), then (P(g) = {"oo", "o", "ollo", "olo", "olyylo", "olylo", "olymmylo", "olymylo", "olymppmylo", "olympmylo"}).
Given a palindrome generator (g) and a string (s), your task is to determine how many times strings from (P(g)) appear as substrings in (s). Specifically, you need to find the number of pairs ((i, j)) such that (s[i..j]) is in (P(g)).
Input
The first line of the input file contains the string (g). The second line contains the string (s). Both strings are non-empty and have a length of no more than (100,000) characters.
Output
Output the number of pairs ((i, j)) such that (s[i..j]) is in (P(g)).