← 返回题目列表

Codeforces · 2081/A

A. 数学除法

中文机器翻译题面 查看原题

Ecrade 有一个整数 $$$x$$$。他将以长度为 $$$n$$$ 的二进制数的形式向您显示这个数字。

有两种操作。

  1. 将 $$$x$$$ 替换为 $$$\left\lfloor \dfrac{x}{2}\right\rfloor$$$,其中 $$$\left\lfloor \dfrac{x}{2}\right\rfloor$$$ 是最大整数 $$$\le \dfrac{x}{2}$$$。
  2. 将 $$$x$$$ 替换为 $$$\left\lceil \dfrac{x}{2}\right\rceil$$$,其中 $$$\left\lceil \dfrac{x}{2}\right\rceil$$$ 是最小整数 $$$\ge \dfrac{x}{2}$$$。

Ecrade 将执行多项操作,直到 $$$x$$$ 变为 $$$1$$$。每次,他都会以 $$$\frac{1}{2}$$$ 的概率独立选择执行第一个操作或第二个操作。

Ecrade 想知道他将执行的预期运算次数,以使 $$$x$$$ 等于 $$$1$$$,以 $$$10^9 + 7$$$ 为模。不过,好像有点困难,所以请帮助他!

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 二进制表示形式的 $$$x$$$ 的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串:二进制表示中的数字$$$x$$$,从最高有效位到最低有效位呈现。保证 $$$x$$$ 的最高有效位是 $$$1$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印一个整数,表示 Ecrade 将执行的预期操作数,以使 $$$x$$$ 等于 $$$1$$$,以 $$$10^9+7$$$ 为模。

正式地,令 $$$M = 10^9+7$$$。可以证明,精确答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出这样一个整数 $$$x$$$ 使得 $$$0 \le x \lt M$$$ 和 $$$x \cdot q \equiv p \pmod{M}$$$ 。

示例

输入
复制

3
3
110
3
100
10
1101001011

输出
复制

500000006
2
193359386

注意

为简单起见,我们将第一个操作称为 $$$\text{OPER 1}$$$,将第二个操作称为 $$$\text{OPER 2}$$$。

在第一个测试用例中,$$$x=6$$$,有六种可能的操作系列:

  • $$$6 \xrightarrow{\text{OPER 1}} 3 \xrightarrow{\text{OPER 1}} 1$$$,概率为 $$$\dfrac{1}{4}$$$。
  • $$$6 \xrightarrow{\text{OPER 1}} 3 \xrightarrow{\text{OPER 2}} 2 \xrightarrow{\text{OPER 1}} 1$$$,概率为 $$$\dfrac{1}{8}$$$。
  • $$$6 \xrightarrow{\text{OPER 1}} 3 \xrightarrow{\text{OPER 2}} 2 \xrightarrow{\text{OPER 2}} 1$$$,概率为 $$$\dfrac{1}{8}$$$。
  • $$$6 \xrightarrow{\text{OPER 2}} 3 \xrightarrow{\text{OPER 1}} 1$$$,概率为 $$$\dfrac{1}{4}$$$。
  • $$$6 \xrightarrow{\text{OPER 2}} 3 \xrightarrow{\text{OPER 2}} 2 \xrightarrow{\text{OPER 1}} 1$$$,概率为 $$$\dfrac{1}{8}$$$。
  • $$$6 \xrightarrow{\text{OPER 2}} 3 \xrightarrow{\text{OPER 2}} 2 \xrightarrow{\text{OPER 2}} 1$$$,概率为 $$$\dfrac{1}{8}$$$。

因此,预期的操作数为 $$$2 \cdot \dfrac{1}{4} + 3 \cdot \dfrac{1}{8} + 3 \cdot \dfrac{1}{8} + 2 \cdot \dfrac{1}{4} + 3 \cdot \dfrac{1}{8} + 3 \cdot \dfrac{1}{8} = \dfrac{5}{2} \equiv 500\,000\,006 \pmod{10^9 + 7}$$$。