Deciphering the Mayan script has proven to be more of a challenge than previously thought. For more than two hundred years, not much has been learned. The main results have been obtained over the past 30 years.
Mayan writing is based on small drawings known as icons that represent sounds. Mayan words are usually written with these symbols, which are arranged next to each other in some order.
One of the problems in deciphering the Mayan script is determining this order. When drawing icons for a word, Maya writers sometimes chose positions for icons based on aesthetic considerations rather than specific rules. This has led to the fact that although the sounds for many of the icons are known, archaeologists are not always sure how the recorded word should be pronounced.
Archaeologists are looking for some word W. They know the icons for it, but they don't know all the possible ways to arrange them. Because they know you will be coming to IOI ’06, they are asking for your help. They will give you g the icons that make up the word W, and the sequence S of all the icons in the inscription they are studying, in the order they appear. Help them by counting the number of possible occurrences of the word W.
Quest
Write a program that, given the signs of the word W and the sequence S of the signs of the inscription, counts the number of all possible occurrences of the word W in S, that is, the number of all different positions of consecutive g icons in the sequence S , which are some permutation of the icons of the word W .
Restrictions
1 ≤ g ≤ 3000, g – number of characters in a word W
g ≤ |S| ≤ 3 000 000 where |S| – number of icons in sequence S
Input
The input of the program is data in the following format:
LINE 1: Contains two numbers separated by a space – g and |S|.
LINE 2: Contains g consecutive characters that represent the word W . Valid characters: ‘a’-‘z’ and ‘A’-‘Z’; uppercase and lowercase letters are considered different.
LINE 3: Contains |S| consecutive characters that represent the icons in the label. Valid characters: ‘a’-‘z’ and ‘A’-‘Z’; uppercase and lowercase letters are considered different.
Output
A single line of program output should contain the number of possible occurrences of W in S.
Important for PASCAL programming
By default in FreePascal, a variable of type string has a size limit of 255 characters. If you want to use longer lines, you must add the {$H+} directive to your code, right after the line program ...;.
Examples
input
4 11
cAda
AbrAcadAbRa
output
2