/*
TASK:string
LANG:C++
*/
#include <iostream>
using namespace std;
int f[60][2010];
int m[60][60][2010];
bool u[60];
string a,b;
int N;
int q=1000000;
long long s=0,s1=0;
int main()
{
//	freopen("test.txt","r",stdin);
//	freopen("test1.txt","w",stdout);
	cin>>a>>b;
//	cout<<a<<b<<endl;
	cin>>N;
	int i,j,k;
	for(i=0;i<=55;i++)
		for(j=0;j<=N+1;j++)
				{
				f[i][j]=-1;
				}
	for(i=0;i<=55;i++)
		for(j=0;j<=55;j++)
				for(k=0;k<=N+1;k++)
					m[i][j][k]=-1;
					
		for(j=0;j<b.size();j++)
			{
				if(b[j]>=97)
					{
						if(b[j]==a[0])
							{
								if(a.size()==1)
									m[b[j]-69][b[j]-69][1]=-2;
									else
									m[b[j]-69][b[j]-69][1]=1;
							}
							else m[b[j]-69][b[j]-69][1]=0;
					}
					else
					{
						if(b[j]==a[0])
							{
								if(a.size()==1)
									m[b[j]-39][b[j]-39][1]=-2;
									else
								m[b[j]-39][b[j]-39][1]=1;
							}
							else m[b[j]-39][b[j]-39][1]=0;
					}				
			}
	int l;	
	
		for(i=0;i<b.size();i++)
		{
			for(j=0;j<=N;j++)
				if(b[i]>=97)
				{
				f[b[i]-69][j]=0;
				u[b[i]-69]=1;
				}
				else
				{
					f[b[i]-39][j]=0;
					u[b[i]-39]=1;
				}
		}
		
	for(i=0;i<b.size();i++)
		{
				if(b[i]>=97)
				{
				f[b[i]-69][1]=1;
				}
				else
				{
				f[b[i]-39][j]=1;
				}			
		}
	
	
	
		
for(k=2;k<=N;k++)	
	for(i=0;i<=55;i++)
	if(u[i])
		for(j=0;j<=55;j++)
		if(u[j])
			for(l=0;l<=55;l++)
			if(u[l])
					if(m[i][j][k-1]>=0&&u[i]&&u[j]&&u[l])
					{
						
					if(a[m[i][j][k-1]]>=97)
					{	
					if(l==a[m[i][j][k-1]]-69)
						{
							m[j][l][k]=m[i][j][k-1]+1;
								if(m[j][l][k]==a.size())
									m[j][l][k]=-2;
						}
						else m[j][l][k]=0;
					}
					else{
						if(l==a[m[i][j][k-1]]-39)
						{
							m[j][l][k]=m[i][j][k-1]+1;
								if(m[j][l][k]==a.size())
									m[j][l][k]=-2;
						}
						else m[j][l][k]=0;
						}
					//	cout<<a[m[i][j][k-1]]<<" "<<k<<endl;
					//	cout<<i<<" "<<j<<" "<<l<<" "<<m[i][j][k-1]<<" "<<m[j][l][k]<<" "<<k<<endl;	
					}
				
	for(k=1;k<=N;k++)
		for(i=0;i<=52;i++)
		if(u[i])
			for(j=0;j<=52;j++)
			if(u[j])
				{
					//if(m[i][j][k]!=-1)
					//	cout<<m[i][j][k]<<" "<<i<<" "<<j<<" "<<k<<endl;
					if(m[i][j][k]==-2)
						{
						//	cout<<k<<" "<<i<<" "<<j<<" "<<m[i][j][k]<<endl;
							long long d=1;
							for(l=1;l<=N-k;l++)
								{
								d*=b.size();
								if(d>=q) d%=q;
								}
							s1+=d;
							if(s1>=q)
								s1%=q;		
						}
				}						
									
		
		
	for(i=2;i<=N;i++)
		for(j=0;j<=52;j++)
			{
				if(u[j])
				{
					for(k=0;k<=52;k++)
						{
							if(u[k])
							{
							if(f[k][i-1]!=-1)
								{
									f[j][i]+=f[k][i-1]%q;
									f[j][i]%=q;

								}
							}
						}
				}
		}				
		for(i=0;i<=52;i++)
			{
				if(u[i])
				{s+=(f[i][N]%q);
				s%=q;
				}
			}					
		cout<<s-s1<<endl;	
	return 0;
}
