ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU contest. Petrozavodsk training camp. Summer 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Lunar Code 2

Time limit: 1.0 second
Memory limit: 64 MB
One may recall that a method of data encoding now known as lunar code was invented by lunar programmers during the defensive war against Martians. Even nowadays its slightly modified version is used by the Lunars in the data transmission. The data is represented in the form of matrix M × N containing ones and zeroes. The transferred matrix must satisfy the following check condition: exactly K of its rows and exactly L 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.
The 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 M × N satisfying the check condition is huge for big enough M and N. Can you calculate this number?


The only input line contains 4 integers separated with space: M, N, K, L (1 ≤ M, N ≤ 100000; 0 ≤ KM; 0 ≤ LN).


Output the number of matrices modulo 109 + 7.


2 2 0 0
2 3 1 1
Problem Author: Igor Chevdar
Problem Source: Ural SU Contest. Petrozavodsk Summer Session, August 2008
To submit the solution for this problem go to the Problem set: 1675. Lunar Code 2