{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAs it has been found out recently, all the Berland\u0027s current economical state can be described using a simple table \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e × \u003ci\u003em\u003c/i\u003e\u003c/span\u003e in size. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e — the number of days in each Berland month, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e — the number of months. Thus, a table cell corresponds to a day and a month of the Berland\u0027s year. Each cell will contain either \u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e, or \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e, which means the state\u0027s gains in a particular month, on a particular day. \u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e corresponds to profits, \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e corresponds to losses. It turned out important for successful development to analyze the data on the state of the economy of the previous year, however when the treasurers referred to the archives to retrieve the data, it turned out that the table had been substantially damaged. In some table cells the number values had faded and were impossible to be deciphered. It is known that the number of cells in which the data had been preserved is strictly less than \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003emax\u003c/i\u003e(\u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e)\u003c/span\u003e. However, there is additional information — the product of the numbers in each line and column equaled \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e. Your task is to find out how many different tables may conform to the preserved data. As the answer to the task can be quite large, you have to find it modulo \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 1000\u003c/span\u003e). The second line contains the integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ek\u003c/i\u003e \u0026lt; \u003ci\u003emax\u003c/i\u003e(\u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e)\u003c/span\u003e) — the number of cells in which the data had been preserved. The next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e lines contain the data on the state of the table in the preserved cells. Each line is of the form \"\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e\", where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) — the number of the table row, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eb\u003c/i\u003e ≤ \u003ci\u003em\u003c/i\u003e\u003c/span\u003e) — the number of the column, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e — the value containing in the cell (\u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e or \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e). They are numbered starting from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e. It is guaranteed that no two lines with same \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e values exist. The last line contains an integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003ep\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint the number of different tables that could conform to the preserved data modulo \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Examples","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 2\n0\n100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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 2\n1\n1 1 -1\n100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}