{"problem":{"name":"少项式复合幂","description":{"content":"给定多项式 $f(x)=\\sum_{i=1}^ma_ix^{b_i}$。定义 $f_1(x)=f(x)$，$f_n(x)=f(f_{n-1}(x))$。 给定模数 $p$。有 $q$ 次询问，每次给出 $x,y$，查询 $f_y(x)\\bmod p$ 的值。 **请注意 $m,p$ 的特殊数据范围。**","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9816"},"statements":[{"statement_type":"Markdown","content":"给定多项式 $f(x)=\\sum_{i=1}^ma_ix^{b_i}$。定义 $f_1(x)=f(x)$，$f_n(x)=f(f_{n-1}(x))$。\n\n给定模数 $p$。有 $q$ 次询问，每次给出 $x,y$，查询 $f_y(x)\\bmod p$ 的值。\n\n**请注意 $m,p$ 的特殊数据范围。**\n\n## Input\n\n输入的第一行包含三个正整数 $m,q,p$，分别为 $f$ 的项数，询问次数和给定模数。\n\n随后 $m$ 行，每行读入两个非负整数 $a_i,b_i$，用于描述多项式 $f$。\n\n随后 $q$ 行，每行两个正整数 $x,y$，表示一次询问。\n\n## Output\n\n输出共 $q$ 行，每行包含对应询问的答案。\n\n[samples]\n\n## Background\n\n> I have won everything except your heart.\n\n终于，小 Z 可以玩一年原神了。但在此之前，他决定做出这道题，以纪念自己对【数据删除】的感情。\n\n## Note\n\n#### 样例解释\n\n样例 1 中 $f(x)=3x^3+x+1$。以第 3 次询问为例，$f_1(10)=f(10)=3\\times10^3+10+1=3011\\equiv 29 \\pmod {71}$。\n\n#### 数据范围与约定\n\n|测试点编号|$y$|$m$|$q$|特殊性质|\n|:-:|:-:|:-:|:-:|:-:|\n|$1\\sim 3$|$\\le 10$|$\\le 20$|$\\le 10^3$|无|\n|$4\\sim 7$|$\\le 10^3$|$\\le 20$|$\\le 10^4$|无|\n|$8,9$|$\\le 10^7$|$\\le 1$|$\\le 3\\times 10^5$|A|\n|$10$|$\\le 10^7$|$\\le 1$|$\\le 3\\times 10^5$|无|\n|$11,12$|$\\le 10^7$|$\\le 2$|$\\le 10^5$|A、B|\n|$13$|$\\le 10^7$|$\\le 2$|$\\le 10^5$|B|\n|$14\\sim 16$|$\\le 10^7$|$\\le 20$|$\\le 500$|无|\n|$17\\sim 20$|$\\le 10^7$|$\\le 20$|$\\le 3\\times 10^5$|无|\n- 特殊性质 A：保证 $p$ 为质数。\n- 特殊性质 B：保证 $b_i\\le 1$。\n\n对于所有数据，保证 $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$，$1\\le x,y\\le 10^7$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9816","tags":["倍增","O2优化"],"sample_group":[["3 5 71\n1 1\n3 3\n1 0\n7 5\n9 6\n10 1\n5 6\n7 6","27\n11\n29\n2\n5"]],"created_at":"2026-03-03 11:09:25"}}