{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eDuring the defense war against Martians, lunar programmers\r\ninvented a new method of information encoding. The data are \r\nrepresented in the form of a matrix \u003ci\u003eM\u003c/i\u003e × \u003ci\u003eN\u003c/i\u003e\r\ncontaining ones and zeros. To avoid distortions during \r\ninformation transfer, an interesting mechanism was devised.\r\nNamely, a transferred matrix \u003ci\u003eA\u003c/i\u003e must satisfy the following \r\ncondition: for any \u003ci\u003ei\u003c/i\u003e from 1 to \u003ci\u003eN\u003c/i\u003e − 1, the set\r\n{\u003ci\u003ej\u003c/i\u003e | (\u003ci\u003eA\u003c/i\u003e[\u003ci\u003ej\u003c/i\u003e][\u003ci\u003ei\u003c/i\u003e]\u003d0 and \u003ci\u003eA\u003c/i\u003e[\u003ci\u003ej\u003c/i\u003e][\u003ci\u003ei\u003c/i\u003e+1]\u003d1)} \r\nmust contain not more than \u003ci\u003eK\u003c/i\u003e elements. If a received matrix \r\ndoes not satisfy this condition, then the information \r\ncannot be trusted. This mechanism became widespread \r\nand got the name \"Lunar check condition\".\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 input contains integers \u003ci\u003eM\u003c/i\u003e, \u003ci\u003eN\u003c/i\u003e, and \u003ci\u003eK\u003c/i\u003e\r\n(1 ≤ \u003ci\u003eM\u003c/i\u003e, \u003ci\u003eN\u003c/i\u003e ≤ 40. 0 ≤ \u003ci\u003eK\u003c/i\u003e ≤ \u003ci\u003eM\u003c/i\u003e).\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\"\u003eYou should output the number of different matrices satisfying the Lunar check condition.\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\u003e2 1 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\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\u003e2 2 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Notes","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eBelow are matrices corresponding to sample 2:\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par_pre\"\u003e\u003cpre\u003e10 11 10 11 10 10 11 11 00 01 00 01 00 01 00\r\n10 10 11 11 00 01 00 01 10 10 11 11 00 00 01\r\n\u003c/pre\u003e\u003c/div\u003e"}}]}