Problem G
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.

2 2 3 4

7