ADATEAMS  Ada and Teams
Ada the Ladybug is a well known mathematician. Next week she is going to represent her school in Mathematic Olympiad. There are many schools participating and each of them has many students. Anyway only some of the students and only some of the schools will be availible to participate in the Olympiad. Question is, how many combinations of students can participate in the Olympiad?
More specifically: There are N schools from which exactly A will participate. Moreover there are B students in each school and exactly D of them will participate in the Olympiad.
Ada could count it herself. But this process takes too much time and the limits for schools and students are changing every moment so she has decided to make a program for it (in fact she has decided that you will make the program for her)!
Input
The input contains up to 10^{4} lines, each containing four integers N,A,B,D, 1 ≤ A ≤ N ≤ 10^{6},1 ≤ D ≤ B ≤ 10^{6}
Output
For each line print the number of combination of students, which can participate in the Olympiad. All students and universities are distinguishable, but their order doesn't matter.
Since the anwer might be huge, print it modulo 10^{9}+7 (1000000007)
Example Input
2 1 2 2 2 2 2 1 2 1 2 1 4 3 3 2 4 2 1 1 10 4 12 7 50 30 44 20
Example Output
2 4 4 108 6 625817778 154746653
hide comments
Rafail Loizou:
20210221 22:46:44
@sherlock11 how is that true? 1/2 = 1 / 7 % 5 != (7^(52)) % 5 = 343 % 5 = 3. Do you mean something else? 

adarshgaur:
20210103 12:59:20
Thanks for this big time limit. XD 

gxurav_07:
20200726 18:55:23
How to understand how many queries are there


kaverikr:
20200626 19:00:26
@morass can you please explain the mathematics for the computing the total number of combinations here, I am bit unclear on the concept behind the problem. 

sherlock11:
20180626 20:43:35
just remember 1/a%mod=(a^(mod2))%mod if(mod==prime) 

Vipul Srivastava:
20170430 15:46:37
Last edit: 20170430 15:48:53 

rrm_2016:
20161122 20:53:41
@morass: can u please check my solution...i tried all possible test cases and i am getting right answer ... i think i m doing something wrong with the input format as this is the first time i am trying this kind of input format...please check


rrm_2016:
20161121 22:27:51
Last edit: 20161122 00:22:11 

morass:
20160925 14:22:34
@vikramsr: Good day to you. Problem is, that you update "f" every time you call "C", making the function O(N). Anyway as you can see, you can precalculate "f" (since it is argument independent) making your "C" function O(log(N)) :) Good Luck! 

vikramsr:
20160925 09:58:04
can u plz check my solution.. 
Added by:  Morass 
Date:  20160905 
Time limit:  4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 