{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eА point of \u003ci\u003en\u003c/i\u003e-dimensional space is called \u003ci\u003evalid\u003c/i\u003e if all its coordinates are integers between 0 and \u003ci\u003em\u003c/i\u003e\u0026nbsp;−\u0026nbsp;1, inclusive. Thus, there are \u003ci\u003em\u003csup\u003en\u003c/sup\u003e\u003c/i\u003e different valid points. A \u003ci\u003ehyperrook\u003c/i\u003e can make a \u003ci\u003emove\u003c/i\u003e from valid point \u003ci\u003ea\u003c/i\u003e to valid point \u003ci\u003eb\u003c/i\u003e if \u003ci\u003ea\u003c/i\u003e and \u003ci\u003eb\u003c/i\u003e differ in exactly one coordinate. For example, (0,2,1) → (2,2,1) → (2,2,0) → (2,1,0) represents a sequence of three moves in three-dimensional space.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eA \u003ci\u003eroute\u003c/i\u003e of length \u003ci\u003ed\u003c/i\u003e from point \u003ci\u003et\u003c/i\u003e\u003csub\u003e0\u003c/sub\u003e to point \u003ci\u003et\u003csub\u003ed\u003c/sub\u003e\u003c/i\u003e is a sequence of valid points \u003ci\u003et\u003c/i\u003e\u003csub\u003e0\u003c/sub\u003e, \u003ci\u003et\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e,\u0026nbsp;…, \u003ci\u003et\u003csub\u003ed\u003c/sub\u003e\u003c/i\u003e such that for any \u003ci\u003ei\u003c/i\u003e\r\nfrom {0, 1, …, \u003ci\u003ed\u003c/i\u003e\u0026nbsp;−\u0026nbsp;1} a hyperrook can make a move from point \u003ci\u003et\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e to point \u003ci\u003et\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u0026nbsp;+\u0026nbsp;1\u003c/sub\u003e.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eGiven integers \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e, \u003ci\u003ed\u003c/i\u003e, \u003ci\u003eq\u003c/i\u003e and valid points \u003ci\u003et\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, \u003ci\u003et\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e, …, \u003ci\u003et\u003csub\u003eq\u003c/sub\u003e\u003c/i\u003e you are to find the number of different routes of length \u003ci\u003ed\u003c/i\u003e\r\nfrom \u003ci\u003et\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e to \u003ci\u003et\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e for any pair (\u003ci\u003ei\u003c/i\u003e,\u0026nbsp;\u003ci\u003ej\u003c/i\u003e) where 1 ≤ \u003ci\u003ei\u003c/i\u003e, \u003ci\u003ej\u003c/i\u003e ≤ \u003ci\u003eq\u003c/i\u003e.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains five space-separated integers \u003ci\u003en\u003c/i\u003e \u003cnobr\u003e(1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 50)\u003c/nobr\u003e, \u003ci\u003em\u003c/i\u003e \u003cnobr\u003e(2 ≤ \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e)\u003c/nobr\u003e, \u003ci\u003ed\u003c/i\u003e \u003cnobr\u003e(0 ≤ \u003ci\u003ed\u003c/i\u003e ≤ 10\u003csup\u003e9\u003c/sup\u003e)\u003c/nobr\u003e, \u003ci\u003ep\u003c/i\u003e \u003cnobr\u003e(1 ≤ \u003ci\u003ep\u003c/i\u003e ≤ 10\u003csup\u003e9\u003c/sup\u003e)\u003c/nobr\u003e and \u003ci\u003eq\u003c/i\u003e \u003cnobr\u003e(2 ≤ \u003ci\u003eq\u003c/i\u003e ≤ 50)\u003c/nobr\u003e. Next \u003ci\u003eq\u003c/i\u003e lines contain coordinates of points \u003ci\u003et\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput \u003ci\u003eq\u003c/i\u003e lines each containing \u003ci\u003eq\u003c/i\u003e space-separated integers.\r\nThe \u003ci\u003ej\u003c/i\u003e-th number in the \u003ci\u003ei\u003c/i\u003e-th line should be equal to the number of different routes of length \u003ci\u003ed\u003c/i\u003e from \u003ci\u003et\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e to \u003ci\u003et\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e modulo \u003ci\u003ep\u003c/i\u003e.\u003c/div\u003e\u003c/div\u003e"}},{"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\u003e2 8 4 10000000 4\r\n3 5\r\n0 5\r\n3 7\r\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e896 720 720 560\r\n720 896 560 720\r\n720 560 896 560\r\n560 720 560 896\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\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\u003e3 3 4 10000000 3\r\n0 2 2\r\n1 1 1\r\n1 2 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e90 36 45\r\n36 90 54\r\n45 54 90\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}