1004. 探索宝物

题目描述

玩家准备探索一个神秘房间，最多可以进行 $n$ 次探索。每次探索会消耗 $c$ 个金币，并随机生成一个宝物。宝物的价值是 $[1, m]$ 中的一个整数。对于价值为 $v$ 的宝物，其出现概率为 $P_v$。

一开始，玩家身上没有宝物。每次探索后，玩家会看到新生成宝物的价值。此时玩家可以选择：

替换当前宝物，即丢弃旧宝物，拿走新宝物；

保留当前宝物，即丢弃新宝物。

之后，玩家可以继续消耗金币进行下一次探索，也可以立即结束探险，带着当前身上的宝物离开。

玩家的最终收益定义为最终带走的宝物价值减去探索消耗的金币总数。玩家也可以在尚未进行任何探索时直接结束探险，此时收益为 $0$。

请你求出在最优策略下，玩家最终收益的期望最大值。

输入格式

第一行一个整数 $T$（$1\le T\le 200$），表示数据组数。

对于每组数据，第一行包含三个整数 $n, m, c$（$1 \le n \le 10^9, 1 \le m \le 10^5, 0 \le c \le 10^9$），分别表示最多探索次数、宝物价值上限、每次探索消耗的金币数。

第二行包含 $m$ 个非负整数 $w_1, w_2, \dots, w_m$（$0 \le w_v \le 10^9$）。其中价值为 $v$ 的宝物出现概率为：$P_v = \frac{w_v}{\sum_{i=1}^{m} w_i}$。保证 $\sum_{i=1}^m w_i \bmod (10^9+7) \neq 0$。

对于所有数据，满足 $\sum m\le 10^6$。

输出格式

输出一个整数，表示在最优策略下，玩家最终收益的期望最大值对 $10^9+7$ 取模后的结果。可以证明这个最大值是一个有理数，设为 $\frac{p}{q}$，你需要输出 $p\cdot q^{-1}\bmod (10^9+7)$，其中 $q^{-1}$ 表示 $q$ 在模 $10^9+7$ 意义下的逆元。

样例输入

2
2 3 0
1 1 1
2 6 1
1 1 1 1 1 1

样例输出

444444450
861111120

来源：2026杭电多校-测试专用（电子科大） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1233&pid=1004