Beautiful Substrings

Limits 1s, 512 MB

Given a binary string T (consisting of 0 and 1) of length exactly 26, which indicates a frequency constraints of first 26 lowercase alphabets. T[i] = ‘1’ indicates i’th alphabet can occur at most once and T[i] = ‘0’ indicates i’th alphabet can occur any number of times. String T is 1 indexed and Alphabets are numbered from 1 to 26. 1st alphabet is ‘a’, 2nd alphabet is ‘b’ …….. and 26th alphabet is ‘z’.

Any string is beautiful if all the characters present in it follows the constraint T.

Given a string S consisting of N lowercase alphabets, count the number of beautiful substrings. Two substrings will be considered different for the answer if either the starting or ending index is different.

A substring is a contiguous sequence of characters within a string.

Input

The first line of input contains a string S.

Next line contains the string T.

1 <= Length of S <= 5 * 10^5

Length of T = 26

Output

Output the number of beautiful substrings in the given string.

Sample

InputOutput
abca
10101111111111111111111111
9

In this example, the constraint T indicates, only b and d can occur any number of times & all other character can occur at most once. There are 9 such substrings in the string which follows this constraint.