现在是 2030 年。专业掷硬币已成为互联网上最受欢迎的游戏。最近举办的掷硬币世界锦标赛吸引了来自世界各地创纪录数量的参赛者！共有 $2^k$ 名参赛者在一场单败淘汰赛中争夺“掷硬币世界冠军”的称号。为简单起见，我们将参赛者用 $1$ 到 $2^k$ 的数字进行编号。

在第一阶段，参赛者被两两配对：$1$ 对阵 $2$，$3$ 对阵 $4$，……，$2^k-1$ 对阵 $2^k$。每场比赛的胜者晋级到下一阶段。接下来的每个阶段都以类似的方式进行：剩余的参赛者按其编号排序，然后两两配对进行比赛。最后的第 $k$ 阶段只有一场比赛，决出世界上最好的掷硬币选手。所有参赛者的掷硬币水平几乎完全相同：在任意两名参赛者之间的比赛中，其中一人获胜的概率恰好为 $\frac{1}{2}$。

一个包含 8 名参赛者的单败淘汰制比赛示例。SXMY 是第 X 阶段第 Y 场比赛的简写。

Hedy 错过了比赛的直播，因此她打算在赛后观看所有的录像。她已经知道了所有参赛者的名单（以及他们的编号），但不知道任何比赛的结果。朋友们向 Hedy 推荐了首先观看的 $n$ 场比赛（当然，没有剧透结果！）。她打算先按照特定的顺序观看这 $n$ 场比赛，然后以随机顺序观看所有剩余的比赛。

如果 Hedy 在观看某场比赛之前不知道该场比赛的胜者，她就会认为这场比赛是令人兴奋的。例如，在观看了决赛之后，两场半决赛对她来说都不再令人兴奋，因为她已经看到了半决赛的胜者在决赛中对决。

求在所有可能的比赛结果和观看顺序下，令人兴奋的比赛数量的期望值。

输入格式

输入的第一行包含两个整数 $k$ 和 $n$（$1 \le k \le 30$；$0 \le n \le \min(2^k - 1, 10^5)$）。

接下来的 $n$ 行按 Hedy 计划观看的顺序描述了推荐的比赛。每行包含两个整数 $s_i$ 和 $m_i$，表示该比赛所在的阶段以及该阶段内的比赛编号（$1 \le s_i \le k$；$1 \le m_i \le 2^{k-s_i}$；所有数对 $(s_i, m_i)$ 均不相同）。

输出格式

输出一个实数，表示令人兴奋的比赛数量的期望值。与标准答案的绝对误差或相对误差不应超过 $10^{-9}$。

样例

输入样例 1

2 3
1 1
2 1
1 2

输出样例 1

2.0

输入样例 2

2 1
1 1

输出样例 2

2.5

输入样例 3

3 2
3 1
1 4

输出样例 3

2.25

输入样例 4

4 0

输出样例 4

6.833333333333333

说明

在第一个样例中，不存在随机性。前两场比赛总是令人兴奋的，第三场比赛总是令人不兴奋的。

在第二个样例中，第一场比赛是令人兴奋的。剩余比赛有两种可能的观看顺序。如果另一场半决赛在决赛之前观看，则两场比赛都是令人兴奋的。在另一种情况下，由于 Hedy 在决赛之后观看该半决赛，因此它将不再令人兴奋。期望值为 $1 + \frac{1}{2}(2 + 1) = 2.5$。