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$.

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$).

The output contains an integer representing the total number of different ways to organize all events, modulo $1\, 000\, 000\, 007$.

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 |