{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOne may recall that a method of data encoding now known as lunar code was\r\ninvented by lunar programmers during the defensive war against Martians.\r\nEven nowadays its slightly modified version is used by the Lunars in the data transmission. The data is represented in the form of matrix \u003ci\u003eM\u003c/i\u003e\u0026nbsp;×\u0026nbsp;\u003ci\u003eN\u003c/i\u003e containing ones and zeroes. The transferred matrix must satisfy the following check condition: exactly \u003ci\u003eK\u003c/i\u003e of its rows and exactly \u003ci\u003eL\u003c/i\u003e of its columns should contain zeroes only. If the received matrix does not satisfy this condition, then the data is considered to be corrupted during the transmission.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe Minister of Communications proposed to change the lunar code in his report for the President of the Lunar Federation. He claimed that the number of different messages that can be transmitted is not big enough. The president ordered the Ministry and the Lunar Academy of Sciences to research this question and to decide whether the code should be changed. It turned out that the minister was wrong because the number of binary matrices \u003ci\u003eM\u003c/i\u003e\u0026nbsp;×\u0026nbsp;\u003ci\u003eN\u003c/i\u003e satisfying the check condition is huge for big enough \u003ci\u003eM\u003c/i\u003e and \u003ci\u003eN\u003c/i\u003e. Can you calculate this number?\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 only input line contains 4 integers separated with space: \u003ci\u003eM\u003c/i\u003e, \u003ci\u003eN\u003c/i\u003e, \u003ci\u003eK\u003c/i\u003e, \u003ci\u003eL\u003c/i\u003e\r\n(\u003cnobr\u003e1 ≤ \u003ci\u003eM\u003c/i\u003e, \u003ci\u003eN\u003c/i\u003e ≤ 100000\u003c/nobr\u003e; \u003cnobr\u003e0 ≤ \u003ci\u003eK\u003c/i\u003e ≤ \u003ci\u003eM\u003c/i\u003e\u003c/nobr\u003e; \u003cnobr\u003e0 ≤ \u003ci\u003eL\u003c/i\u003e ≤ \u003ci\u003eN\u003c/i\u003e\u003c/nobr\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\"\u003eOutput the number of matrices modulo 10\u003csup\u003e9\u003c/sup\u003e\u0026nbsp;+\u0026nbsp;7.\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 2 0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\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 3 1 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}