With an increased time limit of ~12s, the problem would be easily solvable using fast/binary exponentiation (also popular as BigMod). If you don't know that technique already, you can look it up in Google or https://cp-algorithms.com/algebra/binary-exp.html
But the complexity of that algorithm is $\displaystyle O(log_{\displaystyle 2}(power))$ which can be as high as 32 in this problem and thus gets a TLE.
The key observation here is that the base of exponentiation is same in all the queries, and we want to do some kind of precalculation to take advantage of that. Furthermore, in each query, we want to do lesser number of iterations than 32.
Now, why is the complexity of binary exponentiation $\displaystyle O(log_{\displaystyle 2}(power))$? Because it takes advantage of base 2 representation of the the power. How exactly can we do this? Suppose we want to find $5^{11}$.
Basically, $\displaystyle 5^{11} = 5^{(1011)_2} \\= 5^{\displaystyle1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0} \\= (5^{\displaystyle2^3})^1 \times (5^{\displaystyle2^2})^0 \times (5^{\displaystyle2^1})^1 \times (5^{\displaystyle2^0})^1$
Now, what if we want to do it in base 3? Then,$\displaystyle 5^{11} = 5^{\displaystyle(102)_3} \\= 5^{\displaystyle1 \times 3^2 + 0 \times 3^1 + 2 \times 3^0} \\= (5^{\displaystyle3^2})^1 \times (5^{\displaystyle3^1})^0 \times (5^{\displaystyle3^0})^2$
But base 3 has an advantage over base 2 in this case. The complexity of exponentiation in base 3 is $\displaystyle O(log_{\displaystyle 3}(power))$ (18 iterations per query in this problem) which is less than $\displaystyle O(log_{\displaystyle 2}(power))$. But, finding $(5^{\displaystyle 3^{\displaystyle 0}})^{\displaystyle 2}$ will require more multiplications and modulo operations. What can we do about that? We can actually precalculate it since the base is same in all queries.
Basically, we precalculate all $(X^{\displaystyle BASE^{\displaystyle i}})^{\displaystyle j}$ so that we can find answer of any query in only $\displaystyle O(log_{\displaystyle BASE}(power))$ complexity.
In setter's solution, $BASE = 33333$ was used which makes time complexity per query $\displaystyle O(log_{\displaystyle 33333}(power))$ i.e. 2 iterations at max.
