对于一个序列 $a_1, a_2, \ldots, a_n$，考虑如下操作 $f$：$f(a)=\{b_1, b_2, \ldots, b_{n-1}\}$，其中 $b_i=|a_i-a_{i+1}|$。
在应用操作 $f$ 共 $n-1$ 次后，记作 $f^{n-1}(a)$，序列将变为仅剩一个元素。
Bobo 有一个长度为 $n$ 的序列 $a$，其中包含 0、1 和 ?。他想知道有多少种方案（模 $10^9+7$）将 ? 替换为 0 或 1，使得 $f^{n-1}(a)=\{1\}$。
输入包含多组测试数据，以文件结束符（EOF）结束。对于每组测试数据：
第一行包含一个非空字符串 $a$，仅由 0、1 和 ? 组成，表示给定的序列。
- $1 \leq |a| \leq 10^6$
- 所有 $|a|$ 的总和不超过 $10^7$。
对于每组测试数据，输出一个整数，表示结果。
样例
输入格式 1
1 ????? 1010?1?0
输出格式 1
1 16 2