/*
TASK: string
LANG: C++
*/
#include <stdio.h>
#include <string.h>

#define MAXL 2048
#define MOD 1000000

int p, tl, ss, ans = 0;
char s[MAXL], t[MAXL];
char tmp[MAXL];
//int dp[MAXL][MAXL][MAXL];

void check(int l)
{ int fl = 0, i, j;

   for(i=0; i<l-ss+1; i++) {
    for(j=0; j<ss; j++) {
             if(tmp[i+j] != s[j])  break;
    }
    if(j == ss) { fl =1; break;}
  }
  if(!fl) ans = (ans%MOD + 1)%MOD;
  return;
}

void gen(int i, int l)
{ int j;

   if(i == l) {check(l); return; }
   for(j=0; j<tl; j++) {
            tmp[i] = t[j];
            gen(i+1, l);
   }
 return;
}

void input()
{
  scanf("%s", &s);
  scanf("%s", &t);
  scanf("%d", &p);
 return;
}
/*
void init()
{
   dp[1][0][1] = 1;
   dp[1][1][0] = 1;
   if(s[0] == s[ss-1]) dp[1][1][1] = 1;
 return;
}
*/
void solve()
{ int i, j, k;

   tl = strlen(t); ss = strlen(s);
   if(p<=2000) {
     gen(0,p);
     printf("%d\n", ans);
   }
    else {
//         init();
         for(i=2; i<=p; i++) {
//          for(t=1; t<=ss; i++)
//                   dp[i][0][s] =
          for(j=1; j<=ss; j++) {
            for(k=1; k<=ss; k++) {
            }
          }
         }
    }
 return;
}

int main()
{
//  freopen("temp.in", "rt", stdin);
//  freopen("temp.out", "wt", stdout);
  input();
  solve();
 return 0;
}

