\(y=\frac{ax+b}{c}\) 在 \(x\in (0,n]\) 中，如果遇到一条 \(x=k\) 的竖线执行 \(R\)，否则执行 \(U\)，如果遇到整点先 \(U\) 在 \(R\)（可以将 \(U,R\) 视作具有结合律的信息），问最后得到的信息是啥。
记作 \(solve(n,a,b,c,U,R)\)，其中 \(0\leq b<c\)。
如果 \(a\geq c\)：此时 \(x\) 每增大 \(1\) 必然碰到 \(\lfloor\frac{a}{b}\rfloor\) 个 \(U\)，同时分子累加 \(a\bmod c\)，所以转移到 \(solve(n,a\bmod c,b,c,U,U^{\lfloor\frac{a}{c}\rfloor}R)\)。
如果 \(a<c\)：记 \(s_i\) 为第 \(i\) 个 \(R\) 前面有多少个 \(U\)，那么 \(s_i=\lfloor\frac{ax+b}{c}\rfloor\)，反过来考虑一个 \(U\) 前面有多少个 \(R\)，那么就有：
\[\lfloor\frac{ax+b}{c}\rfloor<y \\ ax+b<cy \\ x<\frac{cy-b}{a} \\ x\leq \left\lfloor\frac{cy-b-1}{a}\right\rfloor \]所以可以转一下看成 \(y=\frac{cx-b-1}{a}\) 这条直线，然后交换 \(U,R\)。现在有三个问题：
- 新的定义域是啥；
- 最后一个 \(U\) 后面的 \(R\) 没统计上它们有多少个；
- \(-b-1\) 是负数。
挨个解决（这里的 \(U,R\) 都是原问题的，也就是交换前的）：
- 在原问题中一共有 \(m=\lfloor\frac{an+b}{c}\rfloor\) 个 \(U\) 所以新问题的定义域可以视作 \((0,m]\)。
- 那么一共统计到了 \(\left\lfloor\frac{cm-b-1}{a}\right\rfloor\) 个 \(R\)，所以最后需要额外补上 \(n-\left\lfloor\frac{cm-b-1}{a}\right\rfloor\) 个 \(R\)。
- 考虑将第一个 \(U\) 前面的 \(R\) 单独算，在前面补上 \(\lfloor\frac{c-b-1}{a}\rfloor\) 个 \(R\) 和一个 \(U\)。本来分子的积累是 \(-b-1\)，补完 \(U\) 以后分子的积累变成了 \(c-b-1\)，因为这个实际意义是分子每积累到一个 \(a\) 的倍数就多一个 \(R\)，所以要将状态改为 \(y=\frac{cx+((c-b-1)\bmod a)}{a}\)，需要的 \(U\) 少了个一个于是定义域改为 \((0,m-1]\)。
ele qpow(ele x,int y){
ele s;s.mem();
while(y){
if(y&1)s=s*x;
x=x*x;
y>>=1;
}
return s;
}
ele solve(ll n,ll a,ll b,ll c,ele U,ele R){
if(n<=0)return I;
if(a>=c)return solve(n,a%c,b,c,U,qpow(U,a/c)*R);
ll m=((i128)a*n+b)/c;
if(!m)return qpow(R,n);
return qpow(R,(c-b-1)/a)*U*solve(m-1,c,(c-b-1)%a,a,R,U)*qpow(R,n-(c*m-b-1)/a);
}