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 available 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 104 lines, each containing four integers N,A,B,D, 1 ≤ A ≤ N ≤ 106,1 ≤ D ≤ B ≤ 106
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 answer might be huge, print it modulo 109+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
hanstan:
2016-09-13 14:12:36
Nice time limit :P |
|
Piyush Kumar:
2016-09-08 18:10:54
Thanks for the generous time limit :) |
Added by: | Morass |
Date: | 2016-09-05 |
Time limit: | 4s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |