题目描述

某通信系统会把一段二进制信号拆分成若干个 标准信标段。

一个字符串被称为标准信标段，当且仅当它的长度为偶数，并且前一半字符全为 0，后一半字符全为 1。

例如：

• 01 是标准信标段；
• 0011 是标准信标段；
• 000111 是标准信标段。

如果一个字符串可以由若干个标准信标段依次连接而成，那么称这个字符串是 合法编码。

例如，0011、01001101 是合法编码，而 10、010001101 不是合法编码。

现在给定一个由 0、1、? 三种字符组成的字符串 $s$。你需要把每个 ? 独立替换成 0 或 1。

请计算有多少种替换方案，使得替换后的字符串是合法编码。

答案对 $10^9+7$ 取模。

输入格式

输入一行一个字符串 $s$。

输出格式

输出一行一个整数，表示合法替换方案数。

样例 1 输入

0?0????1

样例 1 输出

6

样例 1 解释

以下方案是合法的：

00001111
00011101
01000111
01001101
01010011
01010101

样例 2,3,4,5

见选手目录下：

• string/ex_string.2-5.in
• string/ex_string.2-5.out

其中：

• 样例 2 满足 $|s|\le 3000$；
• 样例 3 满足 $|s|\le 5\times 10^5$，且所有字符都是 ?；
• 样例 4 满足 $|s|\le 5\times 10^5$，且 $s_i\ne$ w；
• 样例 5 满足 $|s|\le 5\times 10^5$。

备注：原题中出现了“$s_i\ne$ w”，但字符集只有 0、1、?，此处疑似原题笔误。为避免改变原题信息，本改写版保留该特殊性质的原文字面内容。

测试点约束

对于所有数据，满足：

并且 $|s|$ 为偶数。

各子任务如下：

• 子任务 1：$|s|\le 20$，无特殊性质，分值 15。
• 子任务 2：$|s|\le 200$，无特殊性质，分值 10。
• 子任务 3：$|s|\le 3000$，无特殊性质，分值 15。
• 子任务 4：$|s|\le 5\times 10^5$，且所有字符都是 ?，分值 5。
• 子任务 5：$|s|\le 5\times 10^5$，且 $s_i\ne$ w，分值 15。
• 子任务 6：$|s|\le 2\times 10^5$，无特殊性质，分值 10。
• 子任务 7：$|s|\le 5\times 10^5$，无特殊性质，分值 10。
• 子任务 8：$|s|\le 10^6$，无特殊性质，分值 10。
• 子任务 9：$|s|\le 5\times 10^6$，无特殊性质，分值 10。