{"problem":{"name":"[_-0 A] 考试","description":{"content":"答题卡有 $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","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9475"},"statements":[{"statement_type":"Markdown","content":"答题卡有 $n (1 \\le n \\le 10^9)$ 行，$m (1 \\le m \\le 10^9)$ 列，共 $nm$ 道题，**从左到右，从上到下，横向排列**。\n\n每道题有 $c (4 \\le c \\le 10^9)$ 个选项。其中，前 $k(0 \\le k \\le nm)$ 道题为单选题，**有且仅有一个**正确选项；后 $nm - k$ 道题为多选题，正确选项个数**严格大于** $1$ 且**严格小于** $c$。\n\n小 $\\mathfrak{g}$ 正确地回答了所有题，但是她不小心把答题卡的方向看反了，从而她的答案排列方式为**从上到下，从左到右，纵向排列**。\n\n题目的评分方式为：选项完全正确得 $1$ 分，多选或错选得 $0$ 分，漏选按比例给分。\n\n形式化地说，若 $A$ 为某道题正确答案选项的集合，$B$ 为答题卡上选项的集合（均为 $\\{1,2,3,\\cdots,c\\}$ 的子集），则该题得分为：\n\n$$\\begin{cases}\\frac{\\lvert B \\rvert}{\\lvert A \\rvert}&\\text{if\\quad}\nB\\sube A\\\\0&\\text{otherwise}\\end{cases}$$\n\n小 $\\mathfrak{g}$ 忘记考试的正确答案是什么了，于是她去问小 $\\mathfrak{f}$，如果考试的正确答案在合法范围内等概率随机，那么自己期望得分是多少。由于结果可能很大，她只需要知道结果对 $10^9+7$ 取模的值。\n\n**题目保证 $c$ 和 $2^c-c-2$ 都不是 $10^9+7$ 的倍数。**\n\n但是小 $\\mathfrak{f}$ 也不会，所以他来求助万能的你。\n\n## Input\n\n一行，四个用空格分隔的整数 $n,m,k,c$，分别表示答题卡的行数，列数，单选题的数量和每道题的选项个数。\n\n## Output\n\n一行，一个整数，表示期望得分，对 $10^9+7$ 取模。\n\n[samples]\n\n## Background\n\n小 $\\mathfrak{g}$ 参加一场考试时，不小心把答题卡填反了。\n\n## Note\n\n**样例 $1$ 解释：**\n\n得分的期望为 $\\frac{67}{25}$，对 $10^9+7$ 取模为 $760000008$。\n\n一种可能的考试的正确答案依次为：\n\n$\\texttt{C,D,B,AD,ABD,BC}$\n\n那么答题卡上应该填写：\n\n| $\\texttt{C}$ | $\\texttt{D}$ | $\\texttt{B}$ |\n| :----------: | :----------: | :----------: |\n| $\\texttt{AD}$ | $\\texttt{ABD}$ | $\\texttt{BC}$ |\n\n实际填写：\n\n| $\\texttt{C}$ | $\\texttt{B}$ | $\\texttt{ABD}$ |\n| :----------: | :----------: | :----------: |\n| $\\texttt{D}$ | $\\texttt{AD}$ | $\\texttt{BC}$ |\n\n答案为 $\\texttt{C}$，填写 $\\texttt{C}$，得 $1$ 分。\n\n答案为 $\\texttt{D}$，填写 $\\texttt{B}$，得 $0$ 分。\n\n答案为 $\\texttt{B}$，填写 $\\texttt{ABD}$，得 $0$ 分。\n\n答案为 $\\texttt{AD}$，填写 $\\texttt{D}$，得 $\\frac{1}{2}$ 分。\n\n答案为 $\\texttt{ABD}$，填写 $\\texttt{AD}$，得 $\\frac{2}{3}$ 分。\n\n答案为 $\\texttt{BC}$，填写 $\\texttt{BC}$，得 $1$ 分。\n\n综上，这种情况下，考试得分为：\n\n$1+0+0+\\frac{1}{2}+\\frac{2}{3}+1=\n\\frac{19}{6}$ 分。\n\n**本题采用捆绑测试且使用子任务依赖。**\n\n| 编号 | 分值 | $n,m\\le$ | $c\\le$ | 性质 | 依赖 |\n| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |\n| $0$ | $0$ | N/A| N/A | 样例 | 无 |\n| $1$ | $5$ | $10^9$ | $10^9$ | A | 无 |\n| $2$ | $5$ | $2$ | $4$ | 无 | 无 |\n| $3$ | $20$ | $10^3$ | $10$ | 无 | $2$ |\n| $4$ | $15$ | $10^9$ | $10$ | 无 | $2,3$ |\n| $5$ | $15$ | $10^3$ | $10^3$ | 无 | $2,3$ |\n| $6$ | $15$ | $10^3$ | $10^5$ | 无 | $2,3,5$ |\n| $7$ | $10$ | $10^3$ | $10^9$ | B | 无 |\n| $8$ | $10$ | $10^3$ | $10^9$ | 无 | $2,3,5,6,7$ |\n| $9$ | $5$ | $10^9$ | $10^9$ | 无 | $0,1,2,3,4,5,6,7,8$ |\n\n特殊性质 A：$n=1$ 或 $m=1$\n\n特殊性质 B：$k=nm-2$","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9475","tags":["O2优化","组合数学","二项式定理","概率论","期望"],"sample_group":[["2 3 3 4","760000008"],["314159265 358979323 84626433832795028 841971693","465094894"]],"created_at":"2026-03-03 11:09:25"}}