{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIn a martian restaurant, there is a choice of \u003ci\u003en\u003c/i\u003e dishes, and a holiday\r\ndinner consists of \u003ci\u003el\u003c/i\u003e dishes. Some of the dishes could appear more than\r\nonce at the holiday dinner, while some other ones could never appear.\r\nDuring the dinner, plates are placed one above another. The waiter\r\nsometimes brings next dishes or takes the empty plates away. However, an\r\nempty plate could not be taken away until all the plates from the next\r\ndelivered dishes are also taken away. Moreover, for some ordered pairs of\r\ndishes there is a Martian custom: first of these dishes can not be brought\r\nwhile the plate from the second dish stands on the table; such pairs are\r\ncalled \u003ci\u003euncommon\u003c/i\u003e.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eLet\u0027s call a \u003ci\u003etime-table\u003c/i\u003e of the waiter the order of bringing dishes\r\nand taking away plates. Thus, there are 2\u003ci\u003el\u003c/i\u003e items in a time-table.\r\nYour task will be to count how many different time-tables exist for a holiday\r\ndinner of \u003ci\u003el\u003c/i\u003e dishes modulo \u003ci\u003ep\u003c/i\u003e.\r\n\r\n\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 of input contains \u003ci\u003ep\u003c/i\u003e (2\u0026nbsp;≤\u0026nbsp;\u003ci\u003ep\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;10\u003csup\u003e4\u003c/sup\u003e), \u003ci\u003et\u003c/i\u003e\r\n(1 ≤ \u003ci\u003et\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;200) which is the number of items in a time table,\r\n\u003ci\u003en\u003c/i\u003e (1\u0026nbsp;≤\u0026nbsp;\u003ci\u003en\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;10) which is the number of dishes at the restaurant\r\nand \u003ci\u003em\u003c/i\u003e (0\u0026nbsp;≤\u0026nbsp;\u003ci\u003em\u003c/i\u003e ≤ 100)\u0026nbsp;— the number of uncommon pairs.\r\nThe next \u003ci\u003em\u003c/i\u003e lines each contain an ordered pair of numbers \u003ci\u003ei\u003c/i\u003e and \u003ci\u003ej\u003c/i\u003e\r\nwhich means that the dish \u003ci\u003ej\u003c/i\u003e could not be brought while the plate from\r\nthe dish \u003ci\u003ei\u003c/i\u003e stands on the table. Note that the number \u003ci\u003et\u003c/i\u003e is even.\r\n\r\n\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 the number of different time-tables modulo \u003ci\u003ep\u003c/i\u003e.\r\n\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\u003e10000 4 2 1\r\n1 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\r\n\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\u003e9999 6 10 2\r\n2 3\r\n6 7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4866\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}