想要有一种数据结构，维护下列信息：

设 $a_i=\begin{cases}p\ \ \ \ \ \ \ i=p^k,p\in \mathbb{P},k\in\mathbb{N}^+\\1\ \ \ \ \ \ \ others\end{cases}$

现在我们有一个值 $m$。

我希望支持两种操作：

给定 $l,r$，求 $\prod_{i=l}^r a_i\bmod m$。

给定 $c$，将 $m$ 改为 $c$。

保证第二个操作最多执行 $10^4$ 次。

$q\le10^6$。

其中 $q$ 为操作次数。

你可以认为时限 $5s$，空间 $1024 MiB$。

允许离线，请问是否有好的做法？

$n\le10^7$，$m\le10^{18}$。

或者有没有办法可以缩小 $q$ 为代价增加 $n$？

比如让 $n\le10^9$?