题目大意
初始是 $x=1$，我们每轮对 $x$ 做一个操作
- 将 $x$ 变为 $k x$，并输出 $x \bmod M$。
- 将 $x$ 变为 $x / k_i$，即取消第 $i$ 次操作，并输出 $x \bmod M$。
保证每个操作 1 的 $k$ 在操作 2 中至多被除一次。
分析
$M$ 并不保证是质数，逆元可能不存在。
可以把操作序列看作一个乘积式，初始情况下全为 $1$。
- 操作 1 即是把第 $i$ 个数变为 $k$。
- 操作 2 即是把第 $i$ 个数变回 $1$。
修改结束后，询问所有数的乘积。单点修改，区间查询，标准的线段树。
因为只询问全体和，zkw 好写的多。
template <class T>
struct SegmentTree {
vector<T> tr;
int N;
SegmentTree(int l, int r) {
int n = r - l + 1;
N = 2 << std::__lg(n);
tr.resize(N * 2 + 2, 1);
}
void pushdown(int i) {
tr[i] = 1ll * tr[i * 2] * tr[i * 2 + 1] % M;
}
void modify(int i, T x) {
tr[i += N] = x;
for (i /= 2; i; i /= 2) {
pushdown(i);
}
}
};