#include<iostream>
using namespace std;
typedef long long ll;
ll a,b,p;
int main()
{
    scanf("%lld%lld%lld",&a,&b,&p);
    if(!b)
    {
        printf("%lld",1%p);
        return 0;
    }
    ll res=1;
    while(b)
    {
        if(b&1)res=res*a%p;
        b>>=1;
        a=a*a%p;
    }
    printf("%lld",res);
    return 0;
}

#include<iostream>
using namespace std;
typedef long long ll;
ll a,b,p;
int main()
{
    scanf("%lld%lld%lld",&a,&b,&p);
    ll res=0;
    while(b)
    {
        if(b&1)res+=a%p;
        res%=p;//这里注意每次都要模p，因为可能本身res和a%p都小于P，但加起来就不小于了，多次累加就会溢出
        a=a*2%p;
        b>>=1;
    }
    printf("%lld",res);
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
const int N=20,M=1<<20;
int weight[N][N];//存某两个点之间的消耗
int f[M][N];//M为二进制压缩后的状态,N为当前停留在哪个点
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)//因为二进制状态压缩下标是从0开始记录的，为了方便调用这里也从下表为0开始记录
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&weight[i][j]);
        }
    }
    memset(f,0x3f,sizeof f);//因为取较小值，要初始化成正无穷
    f[1][0]=0;//在最开始的点没动，起点已经被走过所以状态为1，因为没有走所以消耗为0
    for(int i=1;i<1<<n;i++)//枚举从只走了第一个点到走了所有点的状态
    {
        for(int j=0;j<n;j++)//枚举上一次走的是哪个点
        {
            if(i>>j&1)//如果当前枚举的状态中j已经被走过才可以继续枚举，否则不合法
            {
                for(int k=0;k<n;k++)//枚举上一次走过的是哪个点
                {
                    if(i-(1<<j) >> k&1)f[i][j]=min(f[i][j],f[i-(1<<j)][k]+weight[k][j]);
                    //如果当前枚举的状态中第k个点已经被走过了才算合法，先去掉i再判断是防止k和j重合的情况
                    //当前状态的最小消耗是这一状态枚举过的情况中的最小值和当前状态下的消耗取较小值
                    //当前状态的消耗为走到第k个点的最小消耗加上从第k个点走到第j个点的消耗，并且第k个点的状态为没走过j
                    //如果已经走过j，那么如果再走到j就进行了没必要的消耗
                }
            }
        }
    }
    printf("%d",f[(1<<n)-1][n-1]);//表示每个点都走过的状态是所有点都是1，相当于更高一位的1000……的数减一
                                  //因为有n个点，编号从0开始，所以更高一位就是n位
                                  //最后一个点就是终点
    return 0;
}

/*
位运算有一个特点，即除了位移运算其他运算每一位之间没有关系，不存在进位
因此，我们可以从每一位分析在确保val不大于m的情况下val的每一位应当选择0还是1
根据数据范围，我们可以求出val的二进制位数一定不大于29
因为要考虑到选的数小于等于m，我们应该从高位到低位进行枚举
对于每一位，我们对0和1进行尝试，从相应的n个运算的t中选出对应的位并进行运算算出最终结果
存在4种情况：
0,0      1,0       0,1       1,1
如果选择0能输出1：
    如果选择1也能输出1，我们选择一会导致val偏大，导致后面可以选择1的情况减少，所以我们要选择0
    如果选择1输出0，那一定选0
如果选择0输出了0：
    如果选择1输出了1，如果不选1即使后面全选择1总伤害也不可能大于这一位选择1，因此一定选1
    如果选择1输出了0，那选择一会对val造成不必要的消耗，可能导致后面必须选1才能输出1的情况无法执行，所以也选择0
至此，我们发现了只有0,1的情况下才会选择1，其他情况均选择0
因此，如果选择1那就把答案和val同时加上1左移当前位，如果选择0，那就把答案加上选择0输出的数所以当前位
最后输出答案即可
*/
#include<iostream>
using namespace std;
int n,m;
const int N=100010;
int d[N][2];
int calc(int val,int bit)//val表示第bit位选择0还是1，bit表示第几位
{
    for(int i=1;i<=n;i++)
    {
        int x=(d[i][0]>>bit)&1;//取出第i个位运算第bit位
        //进行相应的运算
        if(d[i][1]==1)val&=x;
        else if(d[i][1]==2)val|=x;
        else if(d[i][1]==3)val^=x;
    }
    return val;//返回第bit位运算的结果
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)//读入要进行的运算
    {
        string op;
        cin>>op;
        if(op=="AND")d[i][1]=1;
        else if(op=="OR")d[i][1]=2;
        else if(op=="XOR")d[i][1]=3;
        scanf("%d",&d[i][0]);
    }
    int val=0,ans=0;//val表示选择的初始攻击，ans表示最终的攻击
    for(int bit=29;bit>=0;bit--)//从高往低枚举，防止超出m
    {
        int res0=calc(0,bit);//求出第bit位选择0输出的值
        int res1=calc(1,bit);//求出第bit位选择1输出的值
        if(res0<res1&&val+(1<<bit)<=m)val+=1<<bit,ans+=1<<bit;
        //如果res0=0,res1=1,并且初始值加上1左移bit位不大于m就选1,初始值和最终答案第bit位同时改成1
        else ans+=res0<<bit;//否则选0,根据输出的值左移bit位的结果给答案该值
    }
    printf("%d",ans);
    return 0;
}

#include<iostream>
using namespace std;
int n,m,res0=0,res1=-1;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        char op[5];
        int t;
        cin>>op;
        scanf("%d",&t);
        if(op[0]=='A')res0&=t,res1&=t;
        else if(op[0]=='O')res0|=t,res1|=t;
        else if(op[0]=='X')res0^=t,res1^=t;
    }
    // int p=0;
    // for(int i=0;(1<<i)<=m;i++)p++;
    //这里想一步到位找到m的二进制位数，其实不行，因为最终攻击不受m限制
    // p++;
    int val=0,ans=0;//val表示选择的初始攻击，ans表示最终的攻击
    for(int bit=29;bit>=0;bit--)//从高往低枚举，防止超出m
    {
        if(!((res0>>bit)&1)&&((res1>>bit)&1)&&(val+(1<<bit)<=m))val+=1<<bit,ans+=1<<bit;
        //如果res0=0,res1=1,并且初始值加上1左移bit位不大于m就选1,初始值和最终答案第bit位同时改成1
        else if((res0>>bit)&1)ans+=1<<bit;
    }
    printf("%d",ans);
    return 0;
}