P9816 Sparse Polynomial Composite Power

> I have won everything except your heart. Finally, Little Z can play Genshin Impact for a year. But before that, he decided to create this problem to commemorate his feelings for [data deleted].

Given a polynomial $f(x)=\sum_{i=1}^m a_i x^{b_i}$. Define $f_1(x)=f(x)$, and $f_n(x)=f(f_{n-1}(x))$. Given a modulus $p$. There are $q$ queries. Each query gives $x,y$, and asks for the value of $f_y(x)\bmod p$. **Please note the special Constraints for $m,p$.**

The first line contains three positive integers $m,q,p$, representing the number of terms in $f$, the number of queries, and the given modulus. Then follow $m$ lines, each containing two non-negative integers $a_i,b_i$, describing the polynomial $f$. Then follow $q$ lines, each containing two positive integers $x,y$, representing one query.

Output $q$ lines in total, each line containing the answer to the corresponding query.

#### Explanation of the Samples In Sample 1, $f(x)=3x^3+x+1$. Take the 3rd query as an example: $f_1(10)=f(10)=3\times10^3+10+1=3011\equiv 29 \pmod {71}$. #### Constraints and Conventions |Test Point ID|$y$|$m$|$q$|Special Property| |:-:|:-:|:-:|:-:|:-:| |$1\sim 3$|$\le 10$|$\le 20$|$\le 10^3$|None| |$4\sim 7$|$\le 10^3$|$\le 20$|$\le 10^4$|None| |$8,9$|$\le 10^7$|$\le 1$|$\le 3\times 10^5$|A| |$10$|$\le 10^7$|$\le 1$|$\le 3\times 10^5$|None| |$11,12$|$\le 10^7$|$\le 2$|$\le 10^5$|A, B| |$13$|$\le 10^7$|$\le 2$|$\le 10^5$|B| |$14\sim 16$|$\le 10^7$|$\le 20$|$\le 500$|None| |$17\sim 20$|$\le 10^7$|$\le 20$|$\le 3\times 10^5$|None| - Special Property A: $p$ is guaranteed to be a prime. - Special Property B: $b_i\le 1$ is guaranteed. For all testdata, it is guaranteed that $1\le m\le 20$, $0\le a_i,b_i\le 10^5$, $2\le p\le 10^5$, $1\le q\le 3\times 10^5$, and $1\le x,y\le 10^7$. Translated by ChatGPT 5