#abc189f. [abc189_f]Sugoroku2

[abc189_f]Sugoroku2

题目描述

高桥正在玩游戏。

游戏板有 N+1N+1 个方格,编号从 00NN。高桥从方格 00 出发,前往方格 NN

在这个游戏中,我们使用一个可以显示从 11MM 的数字的轮盘,每个数字出现的概率相同。每次操作中,高桥转动轮盘,并按照轮盘上所示的数字前进相应的步数。当他到达或超过方格 NN 时,他获胜。

其中一些方格在高桥停在它们上面时将他送回方格 00。共有 KK 个这样的方格:方格 A1ldotsAKA_1,\\ldots,A_K

求高桥赢得比赛前转动轮盘的次数的期望值。如果无法赢得比赛,请输出 -1

约束条件

  • 输入中的所有值都是整数。
  • 1N1051 \leq N \leq 10^5
  • 1M1051 \leq M \leq 10^5
  • 0K100 \leq K \leq 10
  • 0<A1<<AK<N0 < A_1 < \ldots < A_K < N

输入

从标准输入读入数据,输入格式如下:

NN MM KK A1A_1 \ldots AKA_K

输出

打印高桥赢得比赛前转动轮盘的次数的期望值。当你的输出与我们的答案的绝对误差或相对误差最大为 10310^{-3} 时,将其视为正确。如果无法赢得比赛,请输出 -1


示例输入 1

2 2 0

示例输出 1

1.5000

如果在第一次转动轮盘时出现 11,他将需要两次转动才能获胜;如果在第一次转动轮盘时出现 22,他将需要一次转动才能获胜。因此,转动轮盘的次数的期望值是 1.51.5


示例输入 2

2 2 1
1

示例输出 2

2.0000

如果在第一次转动轮盘时出现 11,他将前进到方格 11,但它会将他送回方格 00。因此,他将继续转动轮盘,直到获得 22 并获胜。他在第 ii 次转动中第一次得到 22 的概率是 frac12i\\frac{1}{2^i},因此转动轮盘的次数的期望值是 $\\sum_{i = 1}^{\\infty} (i \\times \\frac{1}{2^i}) = 2$。


示例输入 3

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

示例输出 3

-1

示例输入 4

100000 2 2
2997 92458

示例输出 4

201932.2222