G-Famished Felbat_2026牛客五一集训派对day2

时间限制：C/C++/Rust/Pascal 10秒，其他语言20秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Note that the context for the problem is simplified and may not be exactly the same as what is in-game. You may directly refer to the end of the problem statement for a formal definition of the problem.

In the popular card-collecting game Hearthstone, there is a mode called Battlegrounds, which is based on the auto battler genre. It allows eight players to compete in each match by recruiting minions over several rounds. In Battlegrounds, there is a special minion called Famished Felbat. It is a sixth-tier demon with stats 9/5 and has the effect of “At the end of your turn, your other demons consume a minion in Bob's Tavern to gain its stats”.

Suppose you are playing Battlegrounds. Currently, you have $n$ demons on the board, and there are $m$ minions in the tavern. You also have the effect of Famished Felbat equipped. You have no coins left, so you must end the turn. You wonder what the expected strength of your warband is after you end the turn.

For the purposes of this problem, we make a few simplifications and specifications as follows:

We assume that each minion is associated with a single positive integer, denoting its stat. When a minion with stat $x$ consumes another minion with stat $y$ , its stat becomes $x+y$ , and the consumed minion disappears.
When you have the effect of Famished Felbat equipped, at the end of your turn, the following happens: Each of your minions, ordering from left to right, sequentially chooses a remaining minion in the tavern uniformly at random and consumes it.
The strength $f(x)$ of a minion with stat $x$ is defined as follows: $f(x)\triangleq\frac{1}{L}\sum\limits_{k=1}^{L}\lceil\frac{x}{k}\rceil,$ where $L$ is some given parameter. (This formula sets strength of a minion with stat $x$ as the expected number of hits a minion with health $x$ can take, assuming the attack of the opponent's minion is uniformly chosen from $[1, L]$ , in the language of real Battleground games.) The strength of your warband is the sum of the strengths over all your minions.

Formally, you have $n$ minions with stats $a_1,a_2,\dots,a_n$ from left to right, respectively. There are $m$ $(n\leq m)$ minions in the tavern with stats $b_1,b_2,\dots,b_m$ , respectively. You are also given the parameter $L$ . At the end of your turn, the following process happens:

Let $S$ be a set initially set as $S=\{1,2,\dots,m\}$ , denoting the indices of remaining minions in the tavern.
For $i=1,2,\dots,n$ , the following happens:

An index $x$ is chosen from $S$ uniformly at random, then set $a_i\gets a_i+b_x$ and $S\gets S\setminus \{x\}$ .

3. The strength of your warband is calculated as $\sum\limits_{i=1}^{n}f(a_i)$ , where $f(x)$ is already defined in the statement above.

You need to calculate the expected strength of your warband after the process above.

输入描述:

The first line contains three integers  , denoting the number of your minions, the number of minions in the tavern, and the parameter for calculating the strength, respectively.
The next line contains  integers  , denoting the stats of your minions.
The next line contains  integers  , denoting the stats of the minions in the tavern.

输出描述:

For each test case, output an integer in a line, denoting the expected strength of your warband after you end the turn. Under the input constraints of this problem, it can be shown that the answer can be written as , where  and  are coprime integers and . You need to output  as an answer, where  is the modular inverse of  with respect to .

示例1

输入

复制

3 3 5
1 2 4
3 5 7

输出

复制

133099258