双六

题目描述

高桥君在玩双六（一种棋盘游戏）。

这个双六有编号为 $0$ 到 $N$ 的 $N+1$ 个格子。 高桥君从格子 $0$ 出发，目标是格子 $N$。

这个双六使用一个从 $1$ 到 $M$ 的 $M$ 种点数等概率出现的转盘。 每个回合，高桥君转动转盘，前进所出点数对应的格数。如果结果到达格子 $N$，或越过格子 $N$，则到达终点（goal）。

此外，有一些格子是「回到起点」，停在这些格子上时会被送回格子 $0$。 这样的格子有 $K$ 个，分别是格子 $A_1,\ldots,A_K$。

请回答高桥君到达终点前转动转盘次数的期望值。 如果无法到达终点，则输出 -1。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$ $K$
$A_1$ $\ldots$ $A_K$

输出格式

输出高桥君到达终点前转动转盘次数的期望值。 另外，与标准答案的绝对误差或相对误差在 $10^{-3}$ 以内即视为正确。 但是，如果无法到达终点，则输出 -1。

样例

2 2 0

1.5000

如果第 $1$ 次转动转盘出 $1$，则需要 $2$ 次；出 $2$ 则需要 $1$ 次到达终点，所以转动转盘次数的期望值为 $1.5$。

2 2 1
1

2.0000

转动转盘出 $1$ 时会移动到格子 $1$，但该格子是「回到起点」，因此会被送回格子 $0$。

因此，需要一直转动转盘直到出 $2$，在第一次出 $2$ 时到达终点。

第 $i$ 次才第一次出 $2$ 的概率为 $\frac{1}{2^i}$，所以转动转盘次数的期望值为 $\sum_{i = 1}^{\infty} (i \times \frac{1}{2^i}) = 2$。

100 6 10
11 12 13 14 15 16 17 18 19 20

-1

100000 2 2
2997 92458

201932.2222

数据范围

• 输入均为整数
• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $0 \leq K \leq 10$
• $0 \lt A_1 \lt \ldots \lt A_K \lt N$