P7486 "Stoi2031" Rainbow

> You are going to leave, I know it is very easy. You say dependence is our obstacle. Even if you let go, can you please not take away my love. Just pretend I only understood at the very end. — "Rainbow"

Hong is a girl who likes to daydream. She thinks the **dependence value** of two positive integers $i, j$ is $\operatorname{lcm}(i,j)^{\operatorname{lcm}(i,j)}$. She defines the product of the **dependence values** of all $i, j$ satisfying $l \le i \le r, l \le j \le r$ as the **obstacle value** of two positive integers $l, r$. Now she gives you a positive integer $n$, and asks you $t$ queries. In each query, you are given two positive integers $l, r$ satisfying $1 \le l \le r \le n$. You need to output the **obstacle value** $ans \bmod{32465177}$.

The first line contains two positive integers $t, n$. The next $t$ lines each contain two positive integers $l_i, r_i$, representing one query.

For each query, output one integer representing the answer.

#### Brief statement: Given $l, r$, compute $\prod\limits_{i=l}^{r}\prod\limits_{j=l}^{r}\operatorname{lcm}(i,j)^{\operatorname{lcm}(i,j)} \bmod{32465177}$. There are multiple queries. #### Sample explanation: For the 1st query, $ans = 1^1 \times (2^2)^3 \times (3^3)^3 \times (6^6)^2$, and $ans \bmod{32465177} = 21072733$. For the 2nd query, $ans = 2^2 \times 3^3 \times (6^6)^2$, and $ans \bmod{32465177} = 12145631$. For the 3rd query, $ans = 7^7 = 823543$. #### Constraints: For $30\%$ of the testdata, $1 \le n \le 10^3, t = 1$. For $60\%$ of the testdata, $1 \le n \le 10^5, t = 1$. For $100\%$ of the testdata, $1 \le n \le 10^6, 1 \le t \le 10, 1 \le l_i \le r_i \le n$. Translated by ChatGPT 5