Misaligned Answer Sheet

The exam answer sheet has \(n\) rows and \(m\) columns (\(1 \le n,m \le 10^9\)), forming a total of \(nm\) questions arranged horizontally (from left to right, top to bottom). Each question has \(c\) options (\(4 \le c \le 10^9\)). The first \(k\) questions (\(0 \le k \le nm\)) are single‐choice questions, meaning that there is exactly one correct option, while the remaining \(nm-k\) questions are multiple‐choice, with the number of correct options being strictly greater than 1 and strictly less than \(c\>.

Little \(\mathfrak{g}\) answered all questions correctly. However, she accidentally filled in her responses on the answer sheet after reading it in the wrong orientation. Instead of filling answers in the natural horizontal order, she filled them in vertically (from top to bottom, then left to right).

The scoring rule for a question is as follows. Let \(A\) be the set of correct options and \(B\) be the set of options marked on the answer sheet (both subsets of \(\{1,2,\dots,c\}\)). The score awarded is

[ score = \begin{cases} \frac{|B|}{|A|}, & \text{if } B \subseteq A,\ 0, & \text{otherwise.} \end{cases} ]

In other words, a fully correct response (where the marked options exactly match the correct answer set) scores \(1\) point; any extra or wrong selections result in a score of \(0\); missing selections are awarded partial credit proportionally.

Because of the misalignment, the answer that was intended for one question may end up attached to a different question. Formally, if we number the questions from \(0\) to \(nm-1\) in horizontal (row‐major) order, and denote by \(f(x)\) the position from which the student's answer comes in the mis‐filled (vertical, column‐major) order, then for a question at horizontal index \(x\) the answer submitted is the one intended for question

[ f(x) = (x \bmod n) \cdot m + \left\lfloor \frac{x}{n} \right\rfloor. ]

The exam key (i.e. the set of correct answers for each question) is generated uniformly at random among all legal answer sets. For single‐choice questions there are exactly \(c\) possibilities, and for multiple‐choice questions the correct answer is chosen uniformly among all subsets of \(\{1,2,\dots,c\}\) of size between \(2\) and \(c-1\); note that the total number of legal multiple‐choice answers is \(2^c-c-2\). It is guaranteed that \(c\) and \(2^c-c-2\) are not divisible by \(10^9+7\).

Let the expected total score be computed by summing the individual expected scores for each question. After some analysis one can show that the final answer can be expressed as

[ E = \frac{k}{c} + \frac{(nm-k)^2}{nm} \cdot T \pmod{10^9+7}, ]

where

[ T = \frac{3^c-2^{c+1}+1}{2\Bigl(2^c-c-2\Bigr)^2} \pmod{10^9+7}. ]

Your task is to compute the expected total score modulo \(10^9+7\) given the values of \(n\), \(m\), \(c\), and \(k\).

inputFormat

The input consists of a single line containing four space‐separated integers: \(n\), \(m\), \(c\), and \(k\).

outputFormat

Output a single integer, the expected total score modulo \(10^9+7\).

sample

1 1 4 1

250000002