题目描述

现在是 2030 年，职业抛硬币已经成为互联网上最流行的运动。

本届世界锦标赛共有 $2^k$ 名选手，编号为 $1,2,\ldots,2^k$，采用单败淘汰制。

第一阶段中，选手按如下方式两两比赛：

• $1$ 对 $2$；
• $3$ 对 $4$；
• ……
• $2^k-1$ 对 $2^k$。

每场比赛的胜者晋级下一阶段。之后每个阶段的规则相同：仍在比赛中的选手按照编号排序，然后相邻两人配对比赛。

第 $k$ 阶段只有一场决赛，并产生最终冠军。

任意两名选手实力完全相同，因此任意一场比赛中，两名选手各自获胜的概率都恰好为

$$\frac12.$$

对于第 $X$ 阶段的第 $Y$ 场比赛，可以简称为 SXMY。

Hedy 错过了比赛直播，因此准备事后观看全部比赛录像。她知道所有参赛选手的名单和编号，但一开始不知道任何比赛结果。

朋友向她推荐了 $n$ 场比赛，并给定了观看顺序。Hedy 会：

1. 先按照给定顺序观看这 $n$ 场比赛；
2. 再把所有尚未观看的比赛按照一个均匀随机的顺序全部看完。

如果 Hedy 在观看一场比赛之前还不知道这场比赛的胜者是谁，她就认为这场比赛是“精彩的”。

例如，如果她已经看过决赛，那么决赛中的两名选手显然分别是两场半决赛的胜者。因此之后再观看这两场半决赛时，她已经知道其胜者，这些比赛便不再精彩。

请对所有可能的比赛结果和所有可能的随机观看顺序取平均，求 Hedy 观看到的精彩比赛数量的期望。

输入格式

第一行包含两个整数 $k,n$：

$$1\le k\le 30,$$ $$0\le n\le \min(2^k-1,10^5).$$

接下来 $n$ 行按照 Hedy 的固定观看顺序描述朋友推荐的比赛。

每行包含两个整数 $s_i,m_i$，表示第 $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

2.0

样例 2

2 1
1 1

2.5

样例 3

3 2
3 1
1 4

2.25

样例 4

4 0

6.833333333333333

样例说明

在样例 1 中不存在随机性。前两场比赛一定精彩，第三场一定不精彩。

在样例 2 中，第一场比赛一定精彩。剩余两场比赛有两种等概率观看顺序：

• 如果先看半决赛再看决赛，那么两场都精彩；
• 如果先看决赛再看半决赛，那么半决赛不精彩。

因此期望为

$$1+\frac12(2+1)=2.5.$$