{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 计算\u003cvar\u003e(A\u003csub\u003e1\u003csup\u003eB\u003csub\u003e1\u003c/sub\u003e\u003c/sup\u003e\u003c/sub\u003e+A\u003csub\u003e2\u003csup\u003eB\u003csub\u003e2\u003c/sub\u003e\u003c/sup\u003e\u003c/sub\u003e+ ... +A\u003csub\u003eH\u003csup\u003eB\u003csub\u003eH\u003c/sub\u003e\u003c/sup\u003e\u003c/sub\u003e)mod M.\u003c/var\u003e\n \u003c/div\u003e\n \u003c/div\u003e\n \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 输入数据的第一行是一个数字T,它表明该测试数据的组数. 然后是T组测试数据,每组测试数据第一行包含两个整数分别是M和H(1\u003c\u003dH,M\u003c\u003d45000),分别代表模数和项数,接下来正好是H行。在每一行上,正好有两个数字Ai和Bi由空格分隔。两个数字不能同时为零。\n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 对于每个样例输出一行,代表答案\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e3\n16\n4\n2 3\n3 4\n4 5\n5 6\n36123\n1\n2374859 3029382\n17\n1\n3 18132\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e2\n13195\n13\n\u003c/pre\u003e"}}]}