Background

When little $\mathfrak{g}$ took an exam, she accidentally held the answer sheet upside down.

Problem Description

The answer sheet has $n (1 \le n \le 10^9)$ rows and $m (1 \le m \le 10^9)$ columns, for a total of $nm$ questions, arranged from left to right, from top to bottom, row-wise.

Each question has $c (4 \le c \le 10^9)$ options. Among them, the first $k (0 \le k \le nm)$ questions are single-choice questions, with exactly one correct option; the remaining $nm - k$ questions are multiple-choice questions, where the number of correct options is strictly greater than $1$ and strictly less than $c$.

Little $\mathfrak{g}$ answered all questions correctly, but she accidentally viewed the direction of the answer sheet the wrong way, so her answers were arranged from top to bottom, from left to right, column-wise.

The scoring rule is: you get $1$ point if all options are exactly correct; you get $0$ points if you select extra options or select any wrong option; if you miss some correct options, you get partial credit proportional to how many you selected.

Formally, let $A$ be the set of correct options for a question, and let $B$ be the set of options filled on the answer sheet (both are subsets of $\{1,2,3,\cdots,c\}$). Then the score for this question is:

$$\begin{cases}\frac{\lvert B \rvert}{\lvert A \rvert}&\text{if\quad} B\sube A\\0&\text{otherwise}\end{cases}$$

Little $\mathfrak{g}$ forgot what the correct answers were, so she asked little $\mathfrak{f}$. If the exam’s correct answers are chosen uniformly at random among all valid answer keys, what is her expected total score? Since the result may be large, you only need the value modulo $10^9+7$.

It is guaranteed that neither $c$ nor $2^c-c-2$ is a multiple of $10^9+7$.

However, little $\mathfrak{f}$ does not know either, so he asks you for help.

Input Format

One line with four integers $n,m,k,c$ separated by spaces, representing the number of rows and columns of the answer sheet, the number of single-choice questions, and the number of options for each question.

Output Format

One line with one integer, the expected score modulo $10^9+7$.

2 3 3 4

760000008

314159265 358979323 84626433832795028 841971693

465094894

Hint

Sample 1 explanation:

The expected score is $\frac{67}{25}$, and modulo $10^9+7$ it is $760000008$.

One possible correct answer key (in order) is:

$\texttt{C,D,B,AD,ABD,BC}$

Then the answer sheet should be filled as:

$\texttt{C}$	$\texttt{D}$	$\texttt{B}$
$\texttt{AD}$	$\texttt{ABD}$	$\texttt{BC}$

But it was actually filled as:

$\texttt{C}$	$\texttt{B}$	$\texttt{ABD}$
$\texttt{D}$	$\texttt{AD}$	$\texttt{BC}$

Correct answer $\texttt{C}$, filled $\texttt{C}$, score $1$.

Correct answer $\texttt{D}$, filled $\texttt{B}$, score $0$.

Correct answer $\texttt{B}$, filled $\texttt{ABD}$, score $0$.

Correct answer $\texttt{AD}$, filled $\texttt{D}$, score $\frac{1}{2}$.

Correct answer $\texttt{ABD}$, filled $\texttt{AD}$, score $\frac{2}{3}$.

Correct answer $\texttt{BC}$, filled $\texttt{BC}$, score $1$.

Therefore, in this case, the exam score is:

$1+0+0+\frac{1}{2}+\frac{2}{3}+1= \frac{19}{6}$ points.

This problem uses bundled testdata and subtask dependencies.

ID	Points	$n,m\le$	$c\le$	Property	Dependency
$0$		N/A		Sample	None
$1$	$5$	$10^9$		A
$2$		$2$	$4$	None
$3$	$20$	$10^3$	$10$		$2$
$4$	$15$	$10^9$			$2,3$
$5$		$10^3$	$10^3$
$6$			$10^5$		$2,3,5$
$7$	$10$		$10^9$	B	None
$8$				None	$2,3,5,6,7$
$9$	$5$	$10^9$			$0,1,2,3,4,5,6,7,8$

Special property A: $n=1$ or $m=1$.

Special property B: $k=nm-2$.

Translated by ChatGPT 5