{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n div.sampleinteractionread {\n width: 60%;\n margin: 3px 0px 3px 0px;\n }\n div.sampleinteractionread pre {\n margin: 1px 5px 1px 5px;\n border-radius: 5px;\n border: solid 1px rgba(255, 255, 255, 0.25);\n background-color: #cccccc;\n padding: 14px 13px;\n font-family: Courier, monospace;\n font-variant-ligatures: none;\n }\n div.sampleinteractionwrite {\n width: 60%;\n margin: 3px 0px 3px 0px;\n margin-left: auto;\n }\n div.sampleinteractionwrite pre {\n margin: 1px 5px 1px 5px;\n border-radius: 5px;\n border: solid 1px rgba(255, 255, 255, 0.25);\n background-color: #cccccc;\n padding: 14px 13px;\n font-family: Courier, monospace;\n font-variant-ligatures: none;\n }\n table.sample {\n width: 100%;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:20.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/c85a473ded376337e44f55cac1c185bd?v\u003d1725587191\" alt\u003d\"/problems/kingswalk/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eChess is a game in which two sides control pieces in an\n attempt to capture each other’s king. The pieces vary in\n mobility. At the beginning of a game the kings are rather\n vulnerable. They are less mobile than most other pieces and\n they tend to hide behind their pawns. Like in real life, as\n soon as both queens have left the game it is time for the kings\n to come into action. Because there is little threat left for\n the king, he can now move safely around the board. Indeed his\n mobility seems to be quite strong at this stage making him one\n of the more dangerous pieces. Your task is to measure the\n mobility of the king in the endgame.\u003c/p\u003e\n\n \u003cp\u003eConsider a chess board of \u003cspan class\u003d\"tex2jax_process\"\u003e$N\\times N$\u003c/span\u003e\u0026nbsp;squares. The king is\n the only piece on the board. He starts at a given position and\n wants to go to another given position in the minimum number of\n moves. The king can move to any adjacent square in any\n orthogonal or diagonal direction.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input starts with a line containing an\n integer\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$T$\u003c/span\u003e\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq T \\leq 100$\u003c/span\u003e), the\n number of test cases. Then for each test case:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eOne line with a single integer\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e, the size of the board, where\n \u003cspan class\u003d\"tex2jax_process\"\u003e$2\\le N\\le 5\\,\n 000$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eOne line with four space-separated\n integers\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$X_1, Y_1, X_2,\n Y_2$\u003c/span\u003e, such that \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\le\n X_1, Y_1, X_2, Y_2\\le N$\u003c/span\u003e, where (\u003cspan class\u003d\"tex2jax_process\"\u003e$X_1,Y_1$\u003c/span\u003e) is the square on which\n the king starts and (\u003cspan class\u003d\"tex2jax_process\"\u003e$X_2,Y_2$\u003c/span\u003e) is the square the king\n wants to go to (different from his starting position).\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eFor each test case, output one line with a single integer:\n the number of ways by which the king can reach the destination\n square in the minimum number of moves. As this number can be\n very large, you must reduce your answer modulo \u003cspan class\u003d\"tex2jax_process\"\u003e$5\\, 318\\, 008$\u003c/span\u003e.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\n3\n1 2 3 2\n8\n2 2 7 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}