题目描述

$01$ 串指的是只有 $0,1$ 组成的串。对于一个 $01$ 串$a_{1⋯n}$，它的逆序对是指这样的 $(i,j)$ ，满足 $1 ≤ i < j ≤ n$ 且$a_i > a_j$。如果一个 $01$ 串的逆序对数量为奇数，则称它是一个 好串。例如，串 $1010$ 有 $3$ 个逆序对，它是一个好串；而串 $0100$ 有 $2$ 个逆序对， 它不是一个好串。 定义这样一个函数$f$：对于一个 $01$ 串$s$，如果$s$可以写成$t_1t_2…t_k$的形式（即$k$个串依次连接），并且所有$t_i$都是好串，那么定义$f(s)$ 的值为这样的最小的$k$；否则，定义$f(s) = 0$。 例如：$f(1010) = 1$，因为 $1010$ 本身是一个好串。$f(101010) = 2$，因为 $101010$本身不是好串，但它可以拆成 $101$ 和 $010$。$f(110) = 0$，因为它无法写成若干个好串的连接。 现在有一个长为$n$的 $01$ 串$s$，它共有 $2^n-1$ 个非空子序列。你需要计算这些串的$f$值之和，模$10^9 + 7$。

输入格式

一行一个长度为$n$的 $01$ 串。

输出格式

输出一个数，表示答案。

01010010

148

010010101010101010010101101010101

421025972

样例输入输出 3

见下发文件。

数据规模

共 10 个测试点。

测试点 1 满足$n ≤ 10$。

测试点 2,3 满足$n ≤ 20$。

测试点 4,5,6 满足$n ≤ 10^3$。

对于所有数据，满足 $1 ≤ n ≤ 10^5$。

附件

附件下载