题目背景

让一只猴子在打字机上随意地按键，只要次数足够多，甚至能出现莎士比亚的全套著作。这个论断被称为无限猴子定理。

题目描述

小爱不断地以 $1/2$ 的概率随机生成 0 及 1，直到生成的序列中出现一个给定的模式 $p$ 时停止。请计算停止时 01 序列长度的期望。

输入格式

第一行：单个整数 $n$，表示 $p$ 的长度； 第二行：$n$ 个字符：表示给定的模式 $p$，保证 $p$ 中只含有 0 或 1 。

输出格式

设序列停止时长度的期望为 $P/Q$，其中 $P$ 与 $Q$ 互素，则输出

其中 $Q'$ 满足 $Q'Q\equiv 1\pmod {1,000,000,007}$。

（提示：其实可以证明期望必然为一个整数，所以一定有 $Q'=Q=1$）

1
0

2

样例解释 1

长度为1时停止的概率为0.5，长度为2时停止的概率为0.25，以此类推，期望长度为2

3
000

14

样例解释 2

随机序列为000的概率为0.125，为1000的概率为0.0625，以此类推，期望长度为14

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 20$；
• 对于 $60\%$ 的数据，$1\leq n\leq 2000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 500,000$。