题目描述

高橋君は双六で遊んでいます。

この双六には $0$ から $N$ の番号がついた $N+1$ 個のマスがあります。 高橋君はマス $0$ からスタートし、マス $N$ を目指します。

この双六では、$1$ から $M$ までの $M$ 種類の目が等確率で出るルーレットを使います。 各手番で、高橋君はルーレットを回して出た目の数だけ進みます。この結果マス $N$ に到達するか、マス $N$ を越えて進むことになる場合、ゴールとなります。

また、いくつかのマスは「振り出しに戻る」であり、それらのマスに止まると、マス $0$ まで戻されます。 そのようなマスは $K$ 個あり、マス $A_1,\ldots,A_K$ です。

高橋君がゴールするまでにルーレットを回す回数の期待値を答えてください。 ゴールすることが不可能な場合は、かわりに -1 を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

高橋君がゴールするまでにルーレットを回す回数の期待値を出力せよ。 なお、想定解答との絶対誤差または相対誤差が $10^{-3}$ 以下であれば正解として扱われる。 ただし、ゴールすることが不可能な場合は、かわりに -1 と出力せよ。

题目大意

有一个人想从 $0$ 号格子走到 $N$ 号格子，每轮等概率从 $[1, M]$ 中选择一个正整数 $x$，从当前位置 $i$ 到位置 $i + x$，当前位置大于等于 $N$ 则游戏结束，有 $K$ 个特殊位置，到特殊位置会直接传送回位置 $0$（不算轮数），问期望轮数。

$1 \le N, M \le 10^5$

$0 \le K \le 10$

2 2 0

1.5000

2 2 1
1

2.0000

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\ <\ A_1\ <\ \ldots\ <\ A_K\ <\ N$

Sample Explanation 1

$1$ 回目のルーレットで $1$ を出した場合は $2$ 回、$2$ を出した場合は $1$ 回でゴールできるので、ルーレットを回す回数の期待値は $1.5$ です。

Sample Explanation 2

ルーレットで $1$ を出すとマス $1$ に移動しますが、このマスは「振り出しに戻る」なのでマス $0$ に戻されます。 従って、$2$ が出るまでルーレットを回し続け、$2$ が初めて出た時点でゴールすることになります。 $i$ 回目に初めて $2$ が出る確率は $\frac{1}{2^i}$ ですから、ルーレットを回す回数の期待値は $ \sum_{i\ =\ 1}^{\infty}\ (i\ \times\ \frac{1}{2^i})\ =\ 2 $ となります。