시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 8 1 1 14.286%

문제

It is year 2030. Professional coin flipping has become the most popular game on the Internet. Latest coin flipping World Championship gathered the record amount of participants from around the world! There are $2^k$ participants, competing in a single-elimination tournament for the title of the Coin Flipping World Champion. For simplicity, we will refer to participants as numbers from $1$ to $2^k$.

In the first stage, participants are split into pairs: 1 against 2, 3 against 4, ... $2^k - 1$ against $2^k$. The winner of each match advances to the next stage. Every next stage goes on similarly: remaining participants are sorted by their number, then split into pairs to play their matches. The last $k$-th stage is just one match that crowns the world's best coin flipper. All participants' coin-flipping skills are almost identical to each other: in a match with any two participants, the probability of one of them winning is exactly $\frac 12$.

An example of a single-elimination tournament with 8 participants. S$X$M$Y$ is a shorthand for the $Y$-th match of the $X$-th stage.

Hedy missed the live broadcast of the tournament, so she's going to watch all the recordings after the fact. She already knows the list of all participants (and their numbers), but doesn't know any match outcomes. Friends suggested Hedy $n$ matches to watch first (without spoiling the result, of course!). First she is going to watch these $n$ matches in a specific order, then watch all the remaining matches in random order.

Hedy considers a match exciting if she doesn't know the winner of that match before watching it. For example, after watching the final, both semifinals will not be exciting for her, because she will have already seen the semifinals winners competing in the final. 

Find the expected number of exciting matches, averaged over all possible tournament outcomes and watch orders.

입력

The first line of the input contains two integers $k$ and $n$ ($1 \le k \le 30$; $0 \le n \le \min(2^k - 1, 10^5)$). Next $n$ lines describe the suggested matches in order Hedy is going to watch them. Each line contains two integers $s_i$ and $m_i$, the stage and the number of the match within that stage ($1 \le s_i \le k$; $1 \le m_i \le 2^{k-s_i}$; all pairs $(s_i, m_i)$ are distinct).

출력

Print a single real number --- the expected number of exciting matches. The absolute or relative error should not exceed $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

힌트

In the first example, there is no randomness. The first two matches are always exciting, the third one is always not.

In the second example, the first match is exciting. There are two possible orders. In case the semifinal match comes before the final match, both matches are exciting. In the other case, the semifinal will not be exciting as Hedy watches it after the final. The expected value is $1 + \frac 12 (2 + 1) = 2.5$.