Palindrome Substring Score

Given two strings \(s_1\) and \(s_2\), we define the score of \(s_1\) as follows:

For every substring of \(s_1\) with odd length that is a palindrome, add to the score the number of times \(s_2\) occurs (as an overlapping occurrence) in that palindromic substring.

Formally, for every palindromic substring \(s_1[l..r]\) where \(r-l+1\) is odd, if \(s_2\) appears \(k\) times in \(s_1[l..r]\), then the score increases by \(k\). Output the final score modulo \(2^{32}\) (i.e. modulo 4294967296).

Note: Occurrences of \(s_2\) in a substring may overlap.

inputFormat

The input consists of two lines. The first line contains the string \(s_1\) and the second line contains the string \(s_2\). Both strings consist of only lowercase letters.

outputFormat

Output a single integer representing the score of \(s_1\) modulo \(2^{32}\).

sample

aba
a

4