005 - 1

a

mod の値間違えていました．(10^9+7 です)

厳密な問題文の書き方が分からないので読みにくかったらごめんなさい．

問題

0, 1, &, |, ^ からなる式が与えられる．
二項演算子 & は AND 演算を意味し， | は OR 演算， ^ は XOR 演算を意味する．

すべての演算子に対して2つの式は括弧で囲まれていなければならない．

1&1&1&1

という式があった場合

((1&1)&(1&1)) や (((1&1)&1)&1) のように演算子ごとに括弧で囲まれていなければならない．

あなたには括弧を付けて計算結果が 1 になるような方法が何通りあるか 10⁹ +7 で割った余りを計算して欲しい．

入力

S

一行に文字列 S が与えられる．

制約

• 1 ≦ |S| ≦ 201
• |S| は奇数
• S は '0', '1', '&', '|', '^' からなる
• 1文字目からはじまり，奇数文字目は '0' または '1'，偶数文字目は '&', '|', '^' のいずれかである．

出力

一行に演算を好きな順序で行ったときに結果が 1 になるような方法が何通りあるか 10⁹ +7 で割った余りを出力しろ．

入力例 1

入力

1|0|1&0

出力

3

入力例 2

入力

1|0^1&1

出力

3

入力例 3

入力

0|1^1^1^0&1^0&1|1|1^1^0|1&1&0^1^0&1|1|0|1|0|0|1&1^0^1&0^1^0^1&1|0^0|1&1&1&1|0|0^1^1^0|0^0&0&0|0^1|1&1&0|1&1|1&0|0^1&1|1|1|1^0&0&1^0&1&1&1|0&1&1|1^0|0|0^0|1|0|1&1&0&0^1&0^1|0^1^1^1|1|1|1^1&0^0|1|1|1&0&0

出力

407611492

入力例 4

入力

1&1&1&1

出力

5

解説

入力例 1 について以下の3通りが考えられる．

(1|((0|1)&0))
(1|(0|(1&0)))
((1|0)|(1&0))

入力例 2 について以下の3通りが考えられる．

(1|((0^1)&1))
(1|(0^(1&1)))
((1|(0^1))&1)

入力例 4 について以下の 5 通りが考えられる．

((1&1)&(1&1))
(((1&1)&1)&1)
(1&(1&(1&1)))
((1&(1&1))&1)
(1&((1&1)&1))