struct matrix
{
    i64 a[2][2];

    void init(int x)
    {
        clr(a,0);
        if(x) a[0][0]=a[1][1]=1;
    }

    matrix operator*(matrix p)
    {
        matrix ans;
        ans.init(0);
        int i,j,k;
        FOR0(k,2) FOR0(i,2) FOR0(j,2)
        {
            ans.a[i][j]+=a[i][k]*p.a[k][j]%(mod-1);
            ans.a[i][j]%=(mod-1);
        }
        return ans;
    }

    matrix pow(int n)
    {
        matrix ans,p=*this;
        ans.init(1);
        while(n)
        {
            if(n&1) ans=ans*p;
            p=p*p;
            n>>=1;
        }
        return ans;
    }
};

matrix p;
int a,b,n;

i64 Pow(i64 a,i64 b)
{
    i64 ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int main()
{
    p.a[0][0]=p.a[1][0]=p.a[0][1]=1;
    p.a[1][1]=0;
    Rush(a)
    {
        RD(b,n);
        if(n==0) PR(a);
        else if(n==1) PR(b);
        else
        {
            matrix temp=p.pow(n-2);
            int x=(temp.a[0][1]+temp.a[1][1])%(mod-1);
            int y=(temp.a[0][0]+temp.a[1][0])%(mod-1);
            PR(Pow(a,x)*Pow(b,y)%mod);
        }
    }
}