/*
TASK:string
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#define PB push_back
#define MP make_pair
#define X first
#define Y second

using namespace std;

int st[2048];
vector<int> br(2048),br1(2048);

int main()
{
	int i,j,k,l,n,p;
	string T,s;
	cin>>s>>T>>p;
//	s="aaa";
	 n=s.size();
//	T="ab";
	 int t=T.size();
//	map<char,int> h;
//	for (i=0; i<T.size(); t++) h[T[i]]=i;
//	p=6;
	
	if (t==2 && p<=21)
	{
		l=0; bool fl;
		for (i=0; i<n; i++)
		{
		  l<<=1;
		  if (s[i]==T[0]) l|=1;
		}
		int ans=0;
		for (i=0; i<(1<<p); i++)
		{
			k=i; k|=1<<p;
			fl=true;
			while (k>(1<<n))
			{
				if ((k&l)==l) { fl=false; break; }
				k>>=1;
				if (k==1 || k==0) break;
			}
			if (fl) ans++;
		}
		cout<<ans<<"\n";
	}
	
	else
	{
	
	st[0]=1;
	for (i=1; i<=p; i++) st[i]=st[i-1]*t%1000000;
	
	br[0]=t-1;
	br[1]=1;
	for (i=2; i<=n; i++)
	{ l=0;
	  for (j=i; j>0; j--)
	  { br[j]=br[j-1]; l+=br[j]; }
	  br[0]=(st[i]-l)%1000000;
/*	    for (j=0; j<n; j++)
		 cout<<br[j]<<" ";
		cout<<endl; */
    }


	for (i=0; i<p-n; i++)
	{
		br1[0]=0;
		for (j=0; j<n; j++)
		{
 		  br1[j+1]=br[j];
 		  br1[0]+=br[j];
	    }
	    br=br1;
	    for (j=0; j<n; j++)
		 cout<<br[j]<<" ";
		cout<<endl;
	}
	int ans=0;
	for (i=0; i<n; i++)
	 { ans+=br[i]; ans%=1000000; }
	cout<<ans<<"\n";
    }
	
	return 0;
}
