{"trustable":false,"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 有一个大小为$n\\times m$棋盘,一棋子想要从位置 $(1, 1)$ 移动到位置$(n, m)$ 。\n \u003cbr\u003e每次移动能够从位置 $(x_1, y_1)$ 转到位置 $(x_2, y_2)$,前提是只有 $x_1, y_1, x_2, y_2$ 满足 $(x_2 - x_1 )^2+(y_2 - y_1)^2 \u003d 5, ~x_2 \u003e x_1,~y_2 \u003e y_1$。\n \u003cbr\u003e不幸的是,棋盘上有一些障碍。 国际象棋永远不能停留在有障碍物的格子上。\n \u003cbr\u003e我想让你告诉我,国际象棋可以通过多种方式实现其目标。\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"输入由多个测试用例组成。\n\u003cbr\u003e对于每个测试用例:\n\u003cbr\u003e第一行是三个整数,$n, m, r, (1\\leq n, m\\leq 10^{18}, 0 \\leq r\\leq 100)$,表示棋盘的长, 棋盘的高,板上的障碍物的数量。\n\u003cbr\u003e然后按照$r$行,每行有两个整数$x,y(1\\leq x\\leq n, 1\\leq y\\leq m)$,表示障碍物的位置。 请注意,在 $(1, 1)$ 位置从来没有障碍物。"}},{"title":"Output","value":{"format":"HTML","content":"对于每个测试用例,输出一行“Case #x: y”,其中 x 是案例编号,从 1 开始。y 是答案对 $110119$ 取模之后的值。"}},{"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\u003e\u003cpre\u003e1 1 0\n3 3 0\n4 4 1\n2 1\n4 4 1\n3 2\n7 10 2\n1 2\n7 1\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cpre\u003eCase #1: 1\nCase #2: 0\nCase #3: 2\nCase #4: 1\nCase #5: 5\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}