25321번 - yo, i herd u liek ternary operators, so..

문제

진수는 삼항 연산자를 아주 좋아한다. 삼항 연산자는

(condition) ? (value_if_true) : (value_if_false)

와 같이 생긴 연산자로, condition이 참일 경우 value_if_true로 평가되고 아닐 경우 value_if_false로 평가된다.

진수가 삼항 연산자에서 재미있다고 느끼는 점은 삼항 연산자 안에 또 삼항 연산자를 쓸 수 있다는 것이다. 다시 말해 condition과 value에도 삼항 연산자가 들어갈 수 있다.

진수는 삼항 연산자를 너무 좋아한 나머지, 연산자가 삼항 연산자밖에 없는 프로그래밍 언어를 개발하기로 했다. 진수가 개발하는 언어의 특징은, 만약 주어진 식이 여러 가지로 해석될 수 있다면 실행할 때마다 다른 해석을 사용해서 다른 결과를 낼 수도 있다는 것이다. 예를 들어 a?b:c?d:e 는

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

로 해석될 수 있다.

진수는 문득 본인이 작성한 식이 몇 가지 방법으로 해석될 수 있는지 궁금해졌다. 구체적으로 정의하자면,

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

위의 BNF(Backus–Naur form)에서 <expr>로 나타낼 수 있는 문자열 중에서 괄호를 제거하고 비교하였을 때 진수가 작성한 식과 같은 문자열이 되는 경우의 수가 궁금한 것이다.

괄호가 없는 삼항 연산자로만 구성된 식이 주어지면 가능한 해석의 수를 출력하는 프로그램을 작성하자. 해석될 수 있는 방법의 수가 너무 클 수 있으므로, 이 수를 소수인 1ドル,円 000,円 000,円 007$$(=10^9+7)$로 나눈 나머지를 계산한다.

입력

첫 번째 줄에 알파벳 소문자와 ?와 :만으로 이루어진 문자열 $S$가 주어진다. $(5\leq\left\vert S \right\vert\leq 300,円 000)$

주어진 문자열은 적어도 하나 이상의 유효한 식으로 해석될 수 있다.

출력

문제에서 요구하는 수를 1ドル,円 000,円 000,円 007$로 나눈 나머지를 출력한다.

제한

힌트