题目背景

小 $\mathfrak{g}$ 参加一场考试时，不小心把答题卡填反了。

题目描述

答题卡有 $n (1 \le n \le 10^9)$ 行，$m (1 \le m \le 10^9)$ 列，共 $nm$ 道题，从左到右，从上到下，横向排列。

每道题有 $c (4 \le c \le 10^9)$ 个选项。其中，前 $k(0 \le k \le nm)$ 道题为单选题，有且仅有一个正确选项；后 $nm - k$ 道题为多选题，正确选项个数严格大于 $1$ 且严格小于 $c$。

小 $\mathfrak{g}$ 正确地回答了所有题，但是她不小心把答题卡的方向看反了，从而她的答案排列方式为从上到下，从左到右，纵向排列。

题目的评分方式为：选项完全正确得 $1$ 分，多选或错选得 $0$ 分，漏选按比例给分。

形式化地说，若 $A$ 为某道题正确答案选项的集合，$B$ 为答题卡上选项的集合（均为 $\{1,2,3,\cdots,c\}$ 的子集），则该题得分为：

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

小 $\mathfrak{g}$ 忘记考试的正确答案是什么了，于是她去问小 $\mathfrak{f}$，如果考试的正确答案在合法范围内等概率随机，那么自己期望得分是多少。由于结果可能很大，她只需要知道结果对 $10^9+7$ 取模的值。

题目保证 $c$ 和 $2^c-c-2$ 都不是 $10^9+7$ 的倍数。

但是小 $\mathfrak{f}$ 也不会，所以他来求助万能的你。

输入格式

一行，四个用空格分隔的整数 $n,m,k,c$，分别表示答题卡的行数，列数，单选题的数量和每道题的选项个数。

输出格式

一行，一个整数，表示期望得分，对 $10^9+7$ 取模。

2 3 3 4

760000008

314159265 358979323 84626433832795028 841971693

465094894

提示

样例 $1$ 解释：

得分的期望为 $\frac{67}{25}$，对 $10^9+7$ 取模为 $760000008$。

一种可能的考试的正确答案依次为：

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

那么答题卡上应该填写：

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

实际填写：

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

答案为 $\texttt{C}$，填写 $\texttt{C}$，得 $1$ 分。

答案为 $\texttt{D}$，填写 $\texttt{B}$，得 $0$ 分。

答案为 $\texttt{B}$，填写 $\texttt{ABD}$，得 $0$ 分。

答案为 $\texttt{AD}$，填写 $\texttt{D}$，得 $\frac{1}{2}$ 分。

答案为 $\texttt{ABD}$，填写 $\texttt{AD}$，得 $\frac{2}{3}$ 分。

答案为 $\texttt{BC}$，填写 $\texttt{BC}$，得 $1$ 分。

综上，这种情况下，考试得分为：

$1+0+0+\frac{1}{2}+\frac{2}{3}+1= \frac{19}{6}$ 分。

本题采用捆绑测试且使用子任务依赖。

编号	分值	$n,m\le$	$c\le$	性质	依赖
$0$		N/A		样例	无
$1$	$5$	$10^9$		A
$2$		$2$	$4$	无
$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	无
$8$				无	$2,3,5,6,7$
$9$	$5$	$10^9$			$0,1,2,3,4,5,6,7,8$

特殊性质 A：$n=1$ 或 $m=1$

特殊性质 B：$k=nm-2$