Glyph Decoding

Decoding Maya glyphs is much harder than it may seem. Only a small number of glyphs have been fully understood, and serious progress in deciphering them began relatively recently.

A Maya word is made from several pictorial glyphs that represent sounds. These glyphs can be arranged in different positions to form one word.

One reason decoding is difficult is the reading order. Ancient writers did not always arrange the glyphs of a word by a fixed rule; instead, they placed them in whatever order looked visually pleasing. Therefore, even if researchers know the sound of each glyph in a word, they may not know the exact order in which the word was pronounced.

Researchers are looking for a particular word W inside a mural string S. They know the g glyphs that make up W, but they do not know the order in which those glyphs may appear in S.

Given W and S, count how many substrings of S with length g can be formed by rearranging all characters of W.

The first line contains two integers g and |S|, the length of W and the length of S, separated by a space. (1 <= g <= 3000, g <= |S| <= 3,000,000)

The second line contains W, and the third line contains S. Both strings consist only of uppercase and lowercase English letters. Uppercase and lowercase letters are considered different.

Print the number of length-g substrings of S that can be a permutation of W.