{"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\"\u003eMatRush is an ACMer from ZJUT, and he always love to create some special programs. Here we will talk about one of his recent inventions.\u003cbr\u003e\u003cbr\u003eThis special program was called \"Mysterious For\", it was written in C++ language, and contain several simple for-loop instructions as many other programs. As an ACMer, you will often write some for-loop instructions like which is listed below when you are taking an ACM contest.\u003cbr\u003efor (int i \u003d 0; i \u0026lt; n; i++) {\u003cbr\u003e\u0026nbsp;\u0026nbsp;for (int j \u003d i; j \u0026lt; n; j++) {\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;for (int k \u003d j; k \u0026lt; n; k++) {\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;blahblahblah();\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;}\u003cbr\u003e\u0026nbsp;\u0026nbsp;}\u003cbr\u003e}\u003cbr\u003e\u003cbr\u003eNow, MatRush has designed m for-loop instructions in the \"Mysterious For\" program, and each for-loop variable was stored in an array a[], whose length is m.\u003cbr\u003e\u003cbr\u003eThe variable i represents a for-loop instructions is the i-th instruction of the \"Mysterious For\" program.There only two type of for-loop instructions will occur in MatRush\u0027s \"Mysterious For\" program:\u003cbr\u003e\u003cbr\u003e\u003cstrong\u003e1-type:\u003c/strong\u003e if a for-loop belongs to 1-type, it will be an instruction like this:\u003cbr\u003efor (int a[i] \u003d 0; a[i] \u0026lt; n; a[i]++) {\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;...\u003cbr\u003e}\u003cbr\u003e\u003cbr\u003e\u003cstrong\u003e2-type: \u003c/strong\u003eif a for-loop belongs to 2-type, it will be an instruction like this:\u003cbr\u003efor (int a[i] \u003d a[i - 1]; a[i] \u0026lt; n; a[i]++) {\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;...\u003cbr\u003e}\u003cbr\u003e\u003cbr\u003eIn addition, after the deepest for-loop instruction there will be a function called HopeYouCanACIt(), here is what\u0027s inside:\u003cbr\u003evoid HopeYouCanACIt() {\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;puts(\"Bazinga!\");\u003cbr\u003e}\u003cbr\u003e\u003cbr\u003eSo, the \"Mysterious For\" program, obviously, will only print some line of the saying: \"Bazinga!\", as it designed for.\u003cbr\u003e\u003cbr\u003eFor example, we can assume that n equals to 3, and if the program has three 1-type for-loop instructions, then it will run 3\u003csup\u003e3\u003c/sup\u003e\u003d27 times of the function HopeYouCanACIt(), so you will get 27 \"Bazinga!\" in total. But if the program has one 1-type for-loop instruction followed by two 2-type for-loop instructions, then it will run 3+2+1+2+1+1\u003d10 times of that function, so there will be 10 \"Bazinga!\" on the screen.\u003cbr\u003e\u003cbr\u003eNow MatRush has the loop length n and m loop instructions with certain type, then he want to know how many \"Bazinga!\" will appear on the screen, can you help him? The answer is too big sometimes, so you just only to tell him the answer mod his QQ number:364875103.\u003cbr\u003e\u003cbr\u003eAll for-loop instructions are surely nested. Besides, MatRush guaranteed that the first one belongs to the 1-type. That is to say, you can make sure that this program is always valid and finite. There are at most 15 1-type for-loop instructions in each program.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"First, there is an integer T(T\u0026lt;\u003d50), the number of test cases.\u003cbr\u003eFor every case, there are 2 lines.\u003cbr\u003eThe first line is two integer n(1\u0026lt;\u003dn\u0026lt;\u003d1000000) and m(1\u0026lt;\u003dm\u0026lt;\u003d100000) as described above.\u003cbr\u003eThe second line first comes an integer k(1\u0026lt;\u003dk\u0026lt;\u003d15), represents the number of 1-type loop instructions, then follows k distinctive numbers, each number is the i-th 1-type loop instruction\u0027s index(started from 0), you can assume the first one of this k numbers is 0 and all numbers are ascending.\u003cbr\u003eAll none 1-type loop instructions of these m one belongs to 2-type."}},{"title":"Output","value":{"format":"HTML","content":"For each certain \"Mysterious For\" program, output one line, \"Case #T: ans\", where T stands for the case number started with 1, and ans is the number of \"Bazinga!\" mod 364875103."}},{"title":"Sample","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\u003e5\r\n3 3\r\n3 0 1 2\r\n3 3\r\n1 0\r\n3 3\r\n2 0 2\r\n4 4\r\n4 0 1 2 3\r\n10 10\r\n10 0 1 2 3 4 5 6 7 8 9\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 27\r\nCase #2: 10\r\nCase #3: 18\r\nCase #4: 256\r\nCase #5: 148372219\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eFor the third program, the code is like this:\u003cbr\u003efor (int a[0] \u003d 0; a[0] \u0026lt; n; a[0]++) {\u003cbr\u003e\u0026nbsp;\u0026nbsp;for (int a[1] \u003d a[0]; a[1] \u0026lt; n; a[1]++) {\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;for (int a[2] \u003d 0; a[2] \u0026lt; n; a[2]++) {\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;HopeYouCanACIt();\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;}\u003cbr\u003e\u0026nbsp;\u0026nbsp;}\u003cbr\u003e}\u003cbr\u003eBecause n \u003d 3, the answer is 3*3+2*3+1*3\u003d18.\u003cbr\u003e"}}]}