题目描述

若一个字符串 $a$ 只含有数字 $1$、$2$、$3$，定义它的三级跳子序列是指三个下标 $i$、$j$、$k$，满足 $a_i=1$，$a_j=2$、$a_k=3$，且 $i<j<k$。

例如字符串 11232 有 2 个三级跳。

给定一个字符串 $S$，这个串包含数字 $1$、$2$、$3$，且包含一种特殊的字符 ?。每个 ? 都可以自由地替换为数字 $1$、$2$ 或 $3$。

每个问号替换成数字后，将会产生各种字符串。请统计，这些字符串的三级跳子序列的数量之和，由于答案很大，输出答案模 $1,000,000,007$ 的余数。

例如，对于序列 12?3，会产生三种数字字符串：

• 1213 有 $1$ 个三级跳
• 1223 有 $2$ 个三级跳
• 1233 有 $2$ 个三级跳

所以共有 $5$ 个三级跳。

输入格式

• 单个字符串

输出格式

12?3

5

数据范围

记 $|S|$ 表示输入字符串的长度

• 对于 $30\%$ 的数据，$1\leq |S|\leq 10$
• 对于 $60\%$ 的数据，$1\leq |S|\leq 200$
• 对于 $100\%$ 的数据，$1\leq |S|\leq 300,000$

来源

改编自 ABC104D We Love ABC