407700: GYM102878 B Residue Problem

Let function $$$f(i,r,P)$$$ equal the number of pairs of $$$(a,b),0\le a,b \lt P$$$ that satisfy the equation $$$a^r{(b+b^2)}^i\equiv b^i(\mathrm{mod}\; P)$$$, where $$$P$$$ is a prime. Given $$$m$$$ queries, each with $$$Y,N,r,P$$$, anwser $$${{{\displaystyle \prod_{i=1}^{N} Y^{f(i,r,P)_{}}}}}\mod 10^9+7$$$.

First, an integer $$$m, 1 \le m \le 10^5 $$$, indicating the number of queries.

The following $$$m$$$ lines, each with four integers $$$Y,N,r,P$$$,( $$$1e5\le Y \lt 10^9+7$$$, $$$1\le N\lt P$$$, $$$1\le r \le 3$$$, $$$3\le P\lt10^9+7$$$), indicating the input of this query.

Output $$$m$$$ lines, each line with an integer standing for the answer to the corresponding query.

4
100000 1234567 1 999999937
100000 7654321 2 999999929
100000 7777777 3 999999893
100000 7777777 3 999999757

968518472
236321637
770733917
509589974