/*
TASK:string
LANG:C++
*/
#include<stdio.h>
#include<string.h>
int c,x,otg[400];
char a[40],b[40];

int main()
{
scanf("%s%s%d",&a,&b,&c);
if(strlen(b)==2)
{
otg[0]=1;
otg[1]=1;
for(x=2;x<=c+1  ;x++)
{
otg[x]=otg[x-1]+otg[x-2];
otg[x]%=1000000;
}
printf("%d\n",otg[c+1]);
}
return 0;
}

