Problem I
Rectangular City
The festive season is coming and Rectangular City is going to organize $N$ different events for $N$ consecutive days. Rectangular City, as its name suggests, consists of $R \times C$ blocks. Each event will be hosted on a rectangular area within the city. In order to lighten-up the events, the mayor decides to spend some of the budgets to decorate $K$ blocks on the condition that every decorated block must be used in all $N$ events.
The city council is interested in the number of different ways to organize all $N$ events such that it is possible to choose $K$ different blocks to decorate. Two ways are considered different if there exists a day in which the corresponding event is hosted on a different area. Since the answer can be very large, modulo the output by $1\, 000\, 000\, 007$.
Input
The input contains a line with four integers $N$, $R$, $C$, and $K$ ($1 \le N \le 10^6$; $1 \le R, C \le 5\, 000$; $1 \le K \le R \cdot C$).
Output
The output contains an integer representing the total number of different ways to organize all events, modulo $1\, 000\, 000\, 007$.
Explanation
In the Sample Input, the city has $2 \times 3$ blocks, and the mayor decides to decorate $4$ blocks for $2$ different events (days). There are a total of $7$ ways to organize the events.
#1 Day 1: oo. Day 2: oo. Decorated: **.
oo. oo. **.
#2 Day 1: oo. Day 2: ooo Decorated: **.
oo. ooo **.
#3 Day 1: .oo Day 2: .oo Decorated: .**
.oo .oo .**
#4 Day 1: .oo Day 2: ooo Decorated: .**
.oo ooo .**
#5 Day 1: ooo Day 2: oo. Decorated: **.
ooo oo. **.
#6 Day 1: ooo Day 2: .oo Decorated: .**
ooo .oo .**
#7 Day 1: ooo Day 2: ooo Decorated: **.
ooo ooo **.
Note that, in the example above, configuration #7 uses the whole city for both events, thus, the decorated blocks can be any $K$ blocks in the city. The shown decorated blocks are only given as examples.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 2 3 4 |
7 |
