2018 ICPC Asia Singapore Regional Contest

Start

2018-12-12 16:00 AKST

2018 ICPC Asia Singapore Regional Contest

End

2018-12-12 21:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1250 days 18:31:13

5:00:00

0:00:00

Problem GRectangular 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