{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e在前往下一个秘密宝藏藏匿地的路上,数学家发现了一座地图上未知的洞穴。数学家进入了这个洞穴,因为它就在那里。在洞穴深处的某处,她发现了一个带有组合锁和一些数字的宝箱。经过一番研究,数学家发现,正确的锁的组合是通过计算在其中的$n$个苹果中选择$m$个不同的方式,并将其与$M$取模得到的。其中$M$是几个不同质数的乘积。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行有一个整数$T (T \\leq 20)$表示测试用例的数量。\u003cbr\u003e\u003cbr\u003e每个测试用例以一行包含三个整数$n, m, k (1 \\leq m \\leq n \\leq 10^{18}, 1 \\leq k \\leq 10)$开始,其中$k$是质数的数量。接下来的一行是$k$个不同的质数$p_1, . . . , p_k$。保证对于每个$i ∈ \\{1, . . . , k\\}$,$M \u003d p_1 · p_2 · · · p_k ≤ 10^{18}$和$p_i \\leq 10^5$。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出正确的组合结果。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n9 5 2\r\n3 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}