P7486 「Stoi2031」彩虹

> 你要离开 我知道很简单 你说依赖 是我们的阻碍 就算放开 但能不能别没收我的爱 就当我最后才明白 ——《彩虹》

虹是一个喜欢幻想的女孩子。她认为两个正整数 $i,j$ 的 **依赖值** 为 $\operatorname{lcm}(i,j)^{\operatorname{lcm}(i,j)}$。她定义所有满足 $l \le i \le r,l \le j \le r$ 的 $i,j$ 的 **依赖值** 之积为两个正整数 $l,r$ 的 **阻碍值**。现在她给了你一个正整数 $n$，并 $t$ 次询问你两个满足 $1 \le l \le r \le n$ 的正整数 $l,r$ 的 **阻碍值** $ans\bmod{32465177}$。

无

无

#### 简述版题意： 给定 $l,r$，求 $\prod\limits_{i=l}^{r}\prod\limits_{j=l}^{r}\operatorname{lcm}(i,j)^{\operatorname{lcm}(i,j)} \bmod{32465177}$。多次询问。 #### 样例解释： 对于第 $1$ 次询问，$ans=1^1 \times (2^2)^3 \times (3^3)^3 \times (6^6)^2$，$ans \bmod{32465177}=21072733$； 对于第 $2$ 次询问，$ans=2^2 \times 3^3 \times (6^6)^2$，$ans \bmod{32465177}=12145631$； 对于第 $3$ 次询问，$ans=7^7=823543$。 #### 数据范围： 对于 $30\%$ 的数据，$1 \le n \le 10^3,t=1$； 对于 $60\%$ 的数据，$1 \le n \le 10^5,t=1$； 对于 $100\%$ 的数据，$1 \le n \le 10^6,1 \le t \le 10,1 \le l_i \le r_i \le n$。