/*
TASK:string
LANG:C++
*/
#include <iostream>
#include <string.h>
using namespace std;

char s[2001],t[53],sol[2001];
int p,n,cnt,m;

bool check(){
    int i,j;
    for(i=0;i<p;i++){
        for(j=0;(sol[i+j]==s[j])&&(j<m);j++);
        if(j==m) return 0;
    }
    return 1;
}

void func(int q){
    int i;
    if(q==p){
        if(check()){
            cnt++;
            if(cnt==1000000) cnt=0;
        }
        return;
    }
    for(i=0;i<n;i++){
        sol[q]=t[i];
        func(q+1);
    }
}

int main(){
    cin>>s>>t>>p;
    n=strlen(t);
    m=strlen(s);
    func(0);
    cout<<cnt<<"\n";
    return 0;
}
