#include<bits/stdc++.h>
using namespace std;
int isPossible(string s1, string s2,int k)
{
    int cnt=0;
    for(int i=0;i<s2.size();i++)
    {
        int j=i;
        while(s1[j]!=s2[i]) j+=1;
        while(i<j)
        {
            swap(s1[j],s1[j-1]);
            cnt+=1;
            j-=1;
        }

    }
    return cnt;
}
bool isSubsequence(string x,string y)
{
    int j=0;
    for (int i=0;i<x.size() and j<y.size();i++)
    {
        if (y[j]==x[i]) j+=1;
    }
    return(j==y.size());
}
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    assert(n>=1 and n<=10 and m>=1 and m<=10 and k>=0 and k<=1000);
    string S,T,copy_S;
    cin>>S>>T;
    assert(S.size()==n and T.size()==m);
    copy_S=S;
    sort(S.begin(),S.end());
    int ans=0;
    do
    {
        if(isSubsequence(S,T))
        {
            int x=isPossible(S,copy_S,k);
            if(x<=k) ans++;
        }
    }while(next_permutation(S.begin(),S.end()));
    cout<<ans<<'\n';
}