#include<iostream>

#include<cstdio>

#include<cstring>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

#define ll long long

int m[][],a,b,n,t[][];

int temp[][];

void power(int x)

{

    if(x==)

    {

        m[][]=m[][]=;

        m[][]=m[][]=;

        return ;

    }

    if(x==)

    {

        m[][]=a%;

        m[][]=b%;

        m[][]=;

        m[][]=;

        return ;

    }

    power(x>>);

    for(int i=;i<=;i++)

    {

        for(int j=;j<=;j++)

        {

            temp[i][j]=;

            for(int k=;k<=;k++)

            {

                temp[i][j]=(temp[i][j]+(m[i][k]*m[k][j])%)%;

            }

         }

    }

    if(x&)

    {

    for(int i=;i<=;i++)

    {

        for(int j=;j<=;j++)

        {

            m[i][j]=;

            for(int k=;k<=;k++)

            {

                m[i][j]=(m[i][j]+(temp[i][k]*t[k][j])%)%;

            }

         }

    }

}

    else

    {

            for(int i=;i<=;i++)

    {

        for(int j=;j<=;j++)

        {

            m[i][j]=temp[i][j];

         }

    }

    }

    for(int i=;i<=;i++)

    {

        for(int j=;j<=;j++)

        {

            m[i][j]=m[i][j]%;

        }

    }

    return ;

}

int main()

{

  while(scanf("%d%d%d",&a,&b,&n),a||b||n)

  {    

        t[][]=a%;

        t[][]=b%;

        t[][]=;

        t[][]=;

      if(n==||n==)

      {

      printf("1\n");

      continue;

}

      else

      {

          power(n-);

          printf("%d\n",(m[][]+m[][])%);

      }

  }

  return ;

 }