配点 : $600$ 点

問題文

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

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

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

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

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

制約

• 入力はすべて整数
• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $0 \leq K \leq 10$
• $0 < A_1 < \ldots < A_K < N$

入力

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

$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