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

#include <iostream>
#include <string>
using namespace std;

string S, T;
int P;
int ans;

void input ()
{
     cin >> S;
     cin >> T;
     cin >> P;
}

void solve ()
{
     int i, j, k, lamp;
     int Scode=0;
     
     for (i=0; i<S.size(); i++) Scode |= (S[i]==S[0])<<i;
     
     for (i=0; i<(1<<P); i++) {
         for (j=0; j<=P-S.size(); j++) {
             lamp = 1;
             for (k=0; k<S.size(); k++)
                 if (((i>>(j+k))&1) != ((Scode>>k)&1)) lamp = 0;
             
             if (lamp) {
                 ans++;
                 //cout << i << "" << Scode << endl;
                 break;
             }
         }
     }
     
     ans = (1<<P) - ans;
}

int main ()
{
    input ();
    
    if (T.size() == 1) ans=0;
    else solve ();
    
    cout << ans%1000000 << "\n";
    
    return 0;
}
