题目描述

Jinsu 非常喜欢三元运算符。三元运算符通常写作：

(condition) ? (value_if_true) : (value_if_false)

当 condition 为真时，表达式的值为 value_if_true；否则为 value_if_false。

Jinsu 觉得三元运算符最有趣的地方在于：三元运算符的条件和两个返回值本身也可以继续包含三元运算符。

他甚至设计了一门只有三元运算符的编程语言。在这门语言中，如果一个没有括号的表达式存在多种解释方式，那么程序每次运行时都可能采用不同的解释。

例如，表达式：

a?b:c?d:e

既可以解释为：

((a)?(b):(c)) ? (d) : (e)

也可以解释为：

(a) ? (b) : ((c)?(d):(e))

形式化地，合法表达式由以下 BNF 定义：

<expr> ::= (<expr>)?(<expr>):(<expr>) | <variable>
<variable> ::= a | b | c | ... | z

对于一个由小写字母、? 和 : 组成且不含括号的字符串 $S$，考虑所有能够由 <expr> 生成的带括号表达式。将这些表达式的括号全部删除后，若得到的字符串恰好为 $S$，则视为 $S$ 的一种解释方式。

请计算 $S$ 一共有多少种不同的解释方式。答案可能很大，请输出其对质数 $1\,000\,000\,007$ 取模后的结果。

输入格式

第一行包含一个字符串 $S$，仅由小写英文字母、? 和 : 组成。

保证 $S$ 至少存在一种合法解释。

输出格式

输出一个整数，表示 $S$ 的合法解释数量对 $1\,000\,000\,007$ 取模后的结果。

数据范围

• $5\le |S|\le 300\,000$。

样例 1

输入

a?b:c?d:e

输出

2

样例 2

输入

u?c?p:c:h

输出

1