/*
TASK: string
LANG: C
*/

#include<stdio.h>

int main()
{
    char s[2002], t[54];
    long p;
    long suma1 = 1, suma2 = 1;
    long i, j;
    
    gets(s);
    gets(t);
    scanf("%ld", &p);
    
    for(i = 0; i < p; i++) suma1 = suma1 * strlen(t);
    for(j = 0; j < p-strlen(s); j++) suma2 = suma2 * (strlen(t) + 1); 
    
    if(strlen(s) > p) printf("%ld\n", suma1 % 1000000);
    if(strlen(s) == p) printf("%ld\n", suma1%1000000 + 1);
    if(strlen(s) < p) printf("%ld\n", (suma1-suma2)%1000000);
    
    return 0;
}
