/*
TASK:string
LANG:C++
*/
#include <iostream>
#include <string.h>
#include <cstdlib>
using namespace std;
char a[2048],b[2048];
int p,N,M;
int br=0;        
char perm[2048];
int next[2048];

void pre()
{
     next[0]=-1;
     for(int i=0,j=-1;i<N;i++,j++,next[i]=j)
             while(j>=0 && a[i]!=a[j]) j=next[j];
}
bool check()
{
    int i,j;
     for(i=0,j=0;i<p && j<N;i++,j++)
                     while(j>=0 && perm[i]!=a[j]) j=next[j];
     if(j==N) return true;
     else return false;
}
void generate(int pos)
{
     
     if(pos==p)
     {
              if(!check()) br++;
              return;
     }
              
     for(int i=0;i<M;i++)
     {
             perm[pos]=b[i];
             generate(pos+1);
     }
}
          
void Solve()
{
     pre();
     generate(0);
     cout<<br<<endl;
    
     return;
}
     
int main()
{
    cin>>a;
    cin>>b;
    cin>>p;
    N=strlen(a);
    M=strlen(b);
    Solve();
}
    
