Гриша уже несколько несколько недель отрабатывает свои навыки в новомодной онлайн-игре про команду космического корабля, вычисляющую предателей среди них. Так как игра очень популярна, появились игроки, которые договариваются между собой о каких-то коммуницировать заранее. Таких людей называют заговорщиками. Заговорщики действуют по следующему алгоритму. В начале игры каждый из заговорщиков пишет в общий чат строку T — ключ шифрования. Далее в течение игры игрок придумывает строку S, записывает её N раз подряд и отправляет в чат. Для того, чтобы получить зашифрованное сообщение, остальным заговорщикам нужно посчитать, сколько раз в этой повторённой N раз строке S встречается ключ шифрования T. Чат обновляется слишком быстро и Гриша не успевает это сделать руками Грише решить эту задачу. Входные данные В первой строке входных данных записана строка T, содержащая не более 300 символов — ключ шифрования. Во второй строке записана строка S, её длина также не превосходит 300. В третьей строке записано целое число N, 1 ≤ N ≤ 5×106 — количество повторений строки S. Все строки состоят только из заглавных английских букв. Выходные данные Программа должна вывести единственное целое число — количество вхождений строки T в строку S, повторённую N раз. Под одним вхождением подразумевается один выбрать подстроку, то есть несколько подряд идущих символов строки, совпадающих со строкой T, не меняя порядок следования этих символов.