/*
TASK: string
LANG: C++
*/

#include<iostream>
#include<algorithm>
using namespace std;
char T[30],P[30],k[10];
int i,j,n,m,f[35];
void init(){
//	freopen("inp3.txt","rt",stdin);
    char f,s;
    cin>>P>>k>>n;
    s=k[0];


    
    //n=strlen(T);
    m=strlen(P);
    for(i=0;i<m;i++){
    	if(P[i]==s)P[i]='0';
        else P[i]='1';
    }
    //for(i=0;i<m;i++)cout<<P[i];
    //cout<<endl;
}

void prekmp(){
	for(i=1,j=0;i<m;){
    	if(P[i]==P[j]){
            f[i++]=++j;
        }
        else if(j)j=f[j-1];
        else i++;
    }
}

bool kmp(){
	for(i=1;i<=m;i++)f[i]=0;
	prekmp();

    for(i=0,j=0;i<n;){
    	if(T[i]==P[j]){
        	i++;
            j++;
            if(j==m){
            	//cout<<"xaxaxa\n";
                return 1;
            }
            
        }
        else if(j)j=f[j-1];
        else i++;
    }
    return 0;
}
int br;
void back(char pos){
	if(pos>n-1){
    	//check

        if(!kmp()){
            //for(i=0;i<n;i++)cout<<T[i];
            //cout<<endl;
        	br++;
        }
        return;
    }
    T[pos]='0';
    back(pos+1);
    T[pos]='1';
    back(pos+1);
}

void solve(){
//	kmp();
//    for(i=0;i<=m;i++)cout<<f[i]<<" ";
//    cout<<endl;
	back(0);
    cout<<br<<endl;
}

int main(){ //cout<<"------\n";
	init();
    solve();
    return 0;
}

