Let's introduce the designation <image>, 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 > 0), that [q, p] can be obtained from string w.

Input

The first line contains two integers b, d (1 ≤ b, d ≤ 107). 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.

Output

In a single line print an integer — the largest number p. If the required value of p doesn't exist, print 0.

Examples

Input

10 3
abab
bab


Output

3
import java.io.*;
import java.lang.reflect.Array;
import java.math.*;
import java.text.DecimalFormat;
import java.util.*;




public class Main {
    private static char [] A,C;
    private static int b,d;
    private static int [] E,fE;

    public static void main(String[] args) throws Exception {
        IO io = new IO(null, null);
        b = io.getNextInt();
        d = io.getNextInt();
        A = io.getNext().toCharArray();
        C = io.getNext().toCharArray();

        HashSet<Character> HS = new HashSet<>();
        for (char c : A) HS.add(c);
        for (char c : C) if (!HS.contains(c)) {
            io.println(0);
            io.close();
            return;
        }
        E = new int[A.length];

        for (int i = 0;i < A.length;i++) {
            int k = i;
            for (int j = 0;j < C.length;j++) {
                while (A[k%A.length] != C[j])
                    k++;
                k++;
            }
            E[i] = k;
        }

        long [] fE = new long[A.length];

        for (int i = 0;i < A.length;i++) {
            fE[i] = E[i];
            long [] val = new long[A.length];
            int [] visT = new int[A.length];
            int j = 2;
            for (;j <= d;j++) {
                if (visT[(int)(fE[i]%A.length)] != 0) break;
                visT[(int)(fE[i]%A.length)] = j;
                val[(int)(fE[i]%A.length)] = fE[i];
                fE[i] += E[(int) (fE[i] % A.length)] - fE[i] % A.length;
            }
            long gain = fE[i] - val[(int)(fE[i]%A.length)];
            int r = d - j + 1,len = j - visT[(int)(fE[i]%A.length)];
            fE[i] += (r/len)*gain;
            r %= len;
            while (r > 0) {
                r--;
                fE[i] += E[(int) (fE[i] % A.length)] - fE[i] % A.length;
            }
        }

//        System.err.println(Arrays.toString(E));
//        System.err.println(Arrays.toString(fE));
        int ans = 0;
        long e = fE[0],N = A.length*b;

        long [] val = new long[A.length];
        boolean [] vis = new boolean[A.length];
        int [] valAns = new int[A.length];

        while (e <= N){
            int j = (int)(e%A.length);
            if (vis[j]) break;
            val[j] = e;
            vis[j] = true;
            valAns[j] = ans;
            ans++;
            e += fE[j] - j;
        }
        int j = (int)(e%A.length);
        int gainAns = ans - valAns[j];
        long gain = e - val[j];
        // e + gain*k <= N
        long k = (N - e)/gain;
        k = Math.max(k,0L);


        ans += gainAns * k;
        e += gain * k;
        while (e <= N){
            ans++;
            e += fE[(int)(e%A.length)] - e%A.length;
        }
        io.println(ans);
        io.close();
    }
}



class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }
    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}
 