题目描述

给你一个长度为 $n$ 的 $01$ 串，以及一个指针，初始时指针在第 $i_0$ 个字符上。每回合随机一个 $0$ 到 $n-1$ 中的数 $j$，如果指针之前在 $i$ 上，就花费 $|i-j|$ 的时间把指针从 $i$ 移动到 $j$ 上，并且把 $01$ 串的第 $j$ 位取反。不停这样随机，直到 $01$ 串变成全 $0$ 或者全 $1$ 为止，问到终止前期望花费的时间是多少？

输入格式

本题有多组数据。

第一行两个整数 $n,t$，表示串长和数据组数，每组数据的串长是相等的。

接下来 $t$ 行，每行一个 $01$ 串和一个整数 $s,i_0$，表示初始时的串和初始位置，$s$ 的长度为 $n$。

输出格式

$t$ 行，每行一个实数表示答案。你的答案被认为是正确的当且仅当，你与标准答案的相对误差小于 $10^{-7}$。

4 4
1000 0
0010 1
0011 2
1010 3

8.9375
8.5625
9.75
10.25

数据范围

对于 $100\%$ 的数据，$n\le 30$，$t\le 10^5$，$0\le i_0 < n$。