/*
TASK:string
LANG:C++
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

#define mod 1000000

using namespace std;

string s,t;
int p;
set<string> ss;

bool is(int a){
        while(a>9){
             if(a%10>t.size())return 0;
             if(a%10==0)return 0;
             a/=10;
        }
        if(a>t.size())return 0;
        if(a==10)return 0;
        return 1;
}

void solve(){
     long long st=0;
    for(int i=0;i<p;i++)
        st=st*10+1;
    long long ed=0;
    for(int i=0;i<p;i++)
        ed=ed*10+t.size();
    for(long long i=st;i<=ed;i++)
        if(is(i)){
          string cur="";
          long long k=i;
          while(k>9){
                cur+=t[k%10-1];
                k/=10;
          }
          cur+=t[k-1];
          string l="";
          do{
             bool tf=1;
             for(int m=0;m<p-s.size()+1;m++){
                 l=cur.substr(m,s.size());
                 if(l==s){
                    tf=0;
                    break;
                 }
             }
             if(tf) ss.insert(cur);
          }while(next_permutation(cur.begin(),cur.end()));
        }
}

int main(){
    cin>>s;
    cin>>t;
    sort(t.begin(),t.end());
    cin>>p;
    int sz=s.size();
    string cur,l;
    if(t.size()==2){
    for(int k=0;k<=p;k++){
        cur="";
    for(int i=0;i<p-k;i++)cur+=t[0];
    for(int j=0;j<k;j++)cur+=t[1];
        l="";
        do{
           bool tf=1;
           for(int m=0;m<p-sz+1;m++){
               l=cur.substr(m,sz);
               if(l==s){
                  tf=0;
                  break;
               }
               }
           if(tf)ss.insert(cur);
        }while(next_permutation(cur.begin(),cur.end()));
    } 
    }
    else if(t.size()==p){
            cur="";
            cur=t;
            l="";
            do{
               bool tf=1;
               for(int m=0;m<p-sz+1;m++){
                   l=cur.substr(m,sz);
                   if(l==s){
                      tf=0;
                      break;
                   }
               }
               if(tf)ss.insert(cur);
            }while(next_permutation(cur.begin(),cur.end()));
    } 
    else solve();       
    cout<<ss.size()<<"\n";
    return 0;
}
