Let's introduce the designation <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/67a1d1d8bf722172a43f9417e83a8026881355d4.png" style="max-width: 100.0%;max-height: 100.0%;"/>, where *x* is a string, *n* is a positive integer and operation " + " is the string concatenation operation. For example, [*abc*, 2] = *abcabc*.

We'll say that string *s* can be obtained from string *t*, if we can remove some characters from string *t* and obtain string *s*. For example, strings *ab* and *aсba* can be obtained from string *xacbac*, and strings *bx* and *aaa* cannot be obtained from it.

Sereja has two strings, *w* = [*a*, *b*] and *q* = [*c*, *d*]. He wants to find such maximum integer *p* (*p* &gt; 0), that [*q*, *p*] can be obtained from string *w*.
The first line contains two integers *b*, *d* (1 ≤ *b*, *d* ≤ 10<sup class="upper-index">7</sup>). The second line contains string *a*. The third line contains string *c*. The given strings are not empty and consist of lowercase English letters. Their lengths do not exceed 100.
import sys
input = sys.stdin.readline

def read_int():
    return int(input())

def read_ints():
    return map(int, input().split())

def read_int_list():
    return [int(i) for i in input().split()]

def read_string():
    return input().strip()

def get_next(s, n):
    next_occ = []
    for i in range(26):
        c = chr(i + 97)
        occ = []
        for j in range(n):
            k = j
            while k < n:
                if s[k] == c:
                    occ.append(k + 1)
                    break
                k += 1
            if k == n:
                occ.append(-1)
        next_occ.append(occ)
    return next_occ

def check(next_occ, n, m, s):
    for i in range(m):
        c = ord(s[i]) - 97
        if next_occ[c][0] == -1:
            return False
    return True

def get_length(next_occ, n, m, s):
    length = []
    for i in range(n):
        count, pos = 0, i
        for j in range(m):
            c = ord(s[j]) - 97
            pos = next_occ[c][pos]
            if pos == n:
                count += 1
                pos = 0
            elif pos == -1:
                count += 1
                pos = next_occ[c][0]
        length.append((count, pos))
    return length

def get_period(length):
    count, num, pos = 0, 0, 0
    seen = dict()
    seen[0] = (0, 0)
    while True:
        num_inc, next_pos = length[pos]
        count, num, pos = count + 1, num + num_inc, next_pos
        if pos in seen:
            prev_num, prev_count = seen[pos]
            num_period = num - prev_num
            count_period = count - prev_count
            return num_period, count_period, pos, prev_num, prev_count
        else:
            seen[pos] = (num, count)
    return 0, 0, 0, 0, 0

def get_count(length, b, pos):
    count = 0
    num = 0
    while num < b:
        num_inc, next_pos = length[pos]
        count, num, pos = count + 1, num + num_inc, next_pos
    if pos != 0:
        count -= 1
    return count

def solve(length, b):
    num_period, count_period, pos, num_offset, count_offset = get_period(length)
    if  num_offset + num_period >= b:
        return get_count(length, b, 0)
    else:
        periods = (b - num_offset)//num_period
        count = count_offset + count_period*periods
        b -= (num_offset + num_period*periods)
        return count + get_count(length, b, pos)

b, d = read_ints()
a, c = read_string(), read_string()
n = len(a)
m = len(c)
next_occ = get_next(a, n)
if not check(next_occ, n, m, c):
    print(0)
else:
    length = get_length(next_occ, n, m, c)
    count = solve(length, b)
    print(count//d)
