题目描述

给定一个由 0 及 1 构成的字符串 $P$， 再给定一个字符串 $T$，$T$ 含有 0，1 及 ?。

现在需要将 T 中的问号 ? 全部替换成 0 或 1。请问有几种替换方式，可以使替换后的 T 中存在 P 为子串。

由于答案很大，输出答案模 1,000,000,007 的余数。

输入格式

• 第一行：单个字符串表示: $P$
• 第二行：单个字符串表示: $S$

输出格式

10
1??

3

样例解释 1

100 101 110

数据范围

记 $|P|$ 表示字符串 $P$ 的长度，$|S|$ 表示字符串 $S$ 的长度：

• $30\%$ 的数据，$1\leq |P|\leq 10$
• $60\%$ 的数据，$1\leq |P|\leq 100$，$1\leq |T|\leq 10000$
• $100\%$ 的数据，$1\leq |P|\leq |T|\leq 500,000$