Grisha has been practicing his skills for several weeks now in a newfangled online game about a crew of a spaceship who detects traitors among them. Since the game is very popular, players have appeared who agree among themselves on some ways to communicate in advance. Such people are called conspirators.
The conspirators act according to the following algorithm. At the beginning of the game, each of the conspirators writes the line T — encryption key. Then, during the game, the player comes up with a string S, writes it down N times in a row and sends it to the chat. In order to receive an encrypted message, the other conspirators need to count how many times the encryption key T occurs in this string S repeated N times. The chat is updated too quickly and Grisha does not have time to do it manually. Help Grisha solve this problem.
Input
The first line of the input contains a string T containing no more than 300 characters — encryption key. The second line contains the string S, its length also does not exceed 300. The third line contains an integer N, 1 <= N <= 5 × 10
6 — the number of repetitions of the string S. All strings consist only of capital English letters.
Imprint
The program should output a single integer — the number of occurrences of string T in string S, repeated N times. One occurrence means one way to select a substring, that is, several consecutive characters of the string that match the string T, without changing the order of these characters.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
MON
AMONGUS
3 |
3 |
|
| 2 |
ABA
BABA
3 |
5 |
If you repeat the string BABA 3 times, you get BABABABABABA.
The substring ABA occurs 5 times in the resulting string:
BABABABABABA, BABABABABABA, BABABABABABA, BABABABABABA, BABABABABABA< /u> |