URI Online Judge | 2578

Ontarama Meraini

By Comissão da VI Maratona Mineira de Programação BR Brasil

Timelimit: 1

Arriving at the opening of the VI Programming Marathon, the teams encountered a somewhat confusing banner saying: "Welcome to VI Ontarama Meraini!". After reading a few times, the most attentive ones realized that it was an anagram of "Maratona Mineira", since Astolfo, the creator of the art, it's a guy that loves anagrams.

An anagram of a word is any other word that is formed by just changing the order of one or more of its letters, for example: "Alergia", "Regalia" and "Galeria" are some of the anagrams of "Alegria".

Astolfo wants to make a joke apart with the competitors involving anagrams, to break the ice and to relax the competitors. To do this, he generated a T-text on his computer, and printed it on a giant strip of paper. In this strip, there are important life lessons that competitors should look for.

He would like to lower the strip so that it fits in his suitcase, since it got huge. However, the grace of the strip is precisely that Astolfo hid in the text some anagrams of a deep message M. So when reducing the strip, Astolfo wants that at least one anagram of M on the final strip. He will do the reduction as follows. First, it has chosen an integer b between 1 and T inclusive, and will cut the first b letters of T, discarding the rest. Then he chooses a second integer and between 1 and b inclusive, and will cut the last and letters of the remaining strip, discarding the other letters. This is the final strip of Astolfo.


Astolfo realized that there could be more than one way of performing this procedure so that the resulting strip contained an anagram of M. Thus he chose T and M in such a way as to conceal an important message in that number of forms as well. So if you also want to know Astolfo's message, just solve the following problem: data T and M, calculate the number of different ways Astolfo has to cut the strip with the procedure described above so that the final strip contains the Less an occurrence of any anagram of P.


The entrance is composed of two lines. The first line contains the text T , composed of only lowercase letters between 'a' and 'z'. The second line contains the message M , also composed of lowercase letters between 'a' and 'z'. (1 ≤ |M||T| ≤ 106)


Print a single integer representing the number of ways Astolfo has to cut strip ends with the text T so that the final strip contains an occurrence of at least one anagram of M at any position.

Input Samples Output Samples