取模
进行 $n$ 次操作，第 $i$ 次操作的结果记为 $a_i$，求出 $a_1 \sim a_n$ 模 $M$ 意义下的值。第 $i$ 次操作是以下四种操作之一：
= v：令 $a_i = v$。+ j k：令 $a_i = a_j + a_k$。* j k：令 $a_i = a_j \times a_k$。^ j k：令 $a_i = a_j^{a_k}$。
$1 \leq n \leq 201307$，$2 \leq M \leq 10^9$，$1 \leq v \leq 10^9$，$1 \leq j,k < i$。
数学、欧拉函数、扩展欧拉定理
如果没有操作四，其余操作可以轻易维护。
因为存在操作四并且存在 $X^Y \bmod M \neq (X \bmod M)^{Y \bmod M}$ 的情况，同时题目不保证模数为质数，考虑扩展欧拉定理。
$$X^Y \equiv \begin{cases} X^Y & Y < \varphi(M) \\ X^{Y \bmod \varphi(M) + \varphi(M)} & Y \geq \varphi(M) \end{cases} (\bmod M)$$
维护 $a_i$ 的同时维护 $a_i \bmod \varphi(M)$ 的值以及 $a_i$ 的实际值是否对 $\varphi(M)$ 取模过的标记，但对于多次操作四，这样维护不足以完成本题。
具体地，维护 $a_i \bmod M$ 和 $a_i \bmod \varphi(M)$ 之后，我们可以成功求出新的 $a_i$ 的值，却无法成功求出新的 $a_i \bmod \varphi(M)$ 的值。因此我们继续维护 $a_i \bmod \varphi(\varphi(M))$ 的值以及它的取模标记，直到模数的欧拉函数值在递归求解过程中降低到 $1$。
维护取模标记导致实现比较繁琐，采用 zmy123456 给出的方法，使用 double 类型变量维护 $a_i$ 的实际值，直接调用 pow 函数计算操作四结果。实际值过大时 double 类型变量取值将会是 $\inf$，不影响后续计算和比较大小的正确性。
总体时间复杂度 $O(\sqrt{V} \log V + n \log^2 V)$。
#include<bits/stdc++.h>
using namespace std;
int n,m,mod[65],a[210'005][65];
double b[210'005];
int phi(int x){
int ret=1,lim=__builtin_sqrt(x);
for(int i=2;i<=lim;i++) if(x%i==0){
x/=i,ret*=i-1;
while(x%i==0) x/=i,ret*=i;
}
if(x!=1) ret*=x-1,x=1;
return ret;
}
void equiv(int x,int k){
b[x]=k;
for(int i=1;i<=m;i++) a[x][i]=k%mod[i];
}
void add(int x,int y,int z){
b[x]=b[y]+b[z];
for(int i=1;i<=m;i++) a[x][i]=(a[y][i]+a[z][i])%mod[i];
}
void mul(int x,int y,int z){
b[x]=b[y]*b[z];
for(int i=1;i<=m;i++) a[x][i]=1ll*a[y][i]*a[z][i]%mod[i];
}
int multiply(int x,int y,int mod){
int ret=1;
while(y){
if(y&1) ret=1ll*ret*x%mod;
x=1ll*x*x%mod,y>>=1;
}
return ret;
}
void expo(int x,int y,int z){
b[x]=pow(b[y],b[z]);
for(int i=m-1;i>=1;i--){
if(b[z]>=mod[i+1]) a[x][i]=multiply(a[y][i],a[z][i+1]+mod[i+1],mod[i]);
else a[x][i]=multiply(a[y][i],a[z][i+1],mod[i]);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>mod[1],m=1;
while(mod[m]!=1) ++m,mod[m]=phi(mod[m-1]);
for(int i=1;i<=n;i++){
static char opt;
static int x,y;
cin>>opt;
if(opt=='='){
cin>>x;
equiv(i,x);
}
else if(opt=='+'){
cin>>x>>y;
add(i,x,y);
}
else if(opt=='*'){
cin>>x>>y;
mul(i,x,y);
}
else{
cin>>x>>y;
expo(i,x,y);
}
}
for(int i=1;i<=n;i++) cout<<a[i][1]<<'\n';
return 0;
}