{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\n\n\t\t\t\t\u003carticle class\u003d\"uoj-article top-buffer-md\"\u003e\n\t\t\t\u003cp\u003e称一个序列 $ (a_1,a_2,\\cdots,a_n) $ 是避免 120 模式的,当且仅当不存在 $ 1\\leq i\u0026lt;j\u0026lt;k\\leq n $ 使得 $ a_k\u0026lt;a_i\u0026lt;a_j $。\u003c/p\u003e\n\u003cp\u003e给定质数 $ P $。$ q $ 次询问,每次给定 $ n,m $,求有多少个长度为 $ n $ 的、值域在 $ [0,m] $ 内的整数序列 $ a $ 是避免 120 模式的,结果对 $ P $ 取模。\u003c/p\u003e\n\n\u003ch3\u003e输入格式\u003c/h3\u003e\n\u003cp\u003e第一行两个整数 $ P,q $,表示模数和询问次数。\u003c/p\u003e\n\u003cp\u003e接下来 $ q $ 行,每行两个整数 $ n,m $,表示一组询问。\u003c/p\u003e\n\n\u003ch3\u003e输出格式\u003c/h3\u003e\n\u003cp\u003e输出共 $ q $ 行,第 $ i $ 行表示第 $ i $ 次询问的答案对 $ P $ 取模的结果。\u003c/p\u003e\n\n\u003ch3\u003e样例数据\u003c/h3\u003e\n\u003cp\u003e见下发文件。\u003c/p\u003e\n\u003ch3\u003e数据范围\u003c/h3\u003e\n\u003cp\u003e对于全部数据,满足 $ 10^8\\leq P\\leq 10^9 $,$ 1\\leq q\\leq 8\\times 10^4 $,$ 1\\leq n\\leq 100 $,$ 0\\leq m\\leq 10^9 $。\u003c/p\u003e\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\u003cp\u003e\u003c/p\u003e\u003cdiv class\u003d\"table-responsive\"\u003e\u003ctable class\u003d\"undefined table table-bordered\"\u003e\u003cthead\u003e\u003ctr\u003e\u003cth style\u003d\"text-align:center;\"\u003e测试点编号\u003c/th\u003e\u003cth style\u003d\"text-align:center;\"\u003e$ n\\leq $\u003c/th\u003e\u003cth style\u003d\"text-align:center;\"\u003e$ m\\leq $\u003c/th\u003e\u003c/tr\u003e\u003c/thead\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 1,2 $\u003c/td\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 16 $\u003c/td\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 16 $\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 3,4 $\u003c/td\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 18 $\u003c/td\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 18 $\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 5,6 $\u003c/td\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 18 $\u003c/td\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 10^9 $\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 7,8 $\u003c/td\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 20 $\u003c/td\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 20 $\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 9,10 $\u003c/td\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 20 $\u003c/td\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 10^9 $\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 11\\sim 16 $\u003c/td\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 100 $\u003c/td\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 100 $\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 17\\sim 20 $\u003c/td\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 100 $\u003c/td\u003e\u003ctd style\u003d\"text-align:center;\"\u003e$ 10^9 $\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\n\u003cp\u003e测试点 $ 11\\sim 20 $ 关于 $ n $ 和 $ q $ 都有梯度。\u003c/p\u003e\n\t\t\u003c/article\u003e\n\t\t\t"}}]}