01 串

题目描述 01 串指的是只有 0,1 组成的串。对于一个 01 串�1⋯� ，它的逆序对是指这样的 �, � ， 满足 1 ≤ � < � ≤ � 且�� > �� 。如果一个 01 串的逆序对数量为奇数，则称它是一个 好串。例如，串 1010 有 3 个逆序对，它是一个好串；而串 0100 有 2 个逆序对， 它不是一个好串。

定义这样一个函数�：对于一个 01 串�，如果�可以写成�1 �2 …��的形式（即�个串依 次连接），并且所有�� 都是好串，那么定义� � 的值为这样的最小的�；否则，定 义� � = 0。

例如：� 1010 = 1，因为 1010 本身是一个好串。� 101010 = 2，因为 101010 本身不是好串，但它可以拆成 101 和 010。� 110 = 0，因为它无法写成若干个好 串的连接。

现在有一个长为�的 01 串�，它共有2� − 1 个非空子序列。你需要计算这些串的� 值之和，模109 + 7。

输入格式 一行一个长度为�的 01 串。

输出格式 输出一个数，表示答案。

样例输入 1 01010010

样例输出 1 148

样例输入 2 010010101010101010010101101010101

样例输出 2 421025972

样例输入输出 3 见下发文件。

数据规模 共 10 个测试点。

测试点 1 满足� ≤ 10。 测试点 2,3 满足� ≤ 20。

测试点 4,5,6 满足� ≤ 103 。

对于所有数据，满足 1 ≤ � ≤ 105 。