問題

背景

数式検索の研究をしていたビッグブリッジ伯爵はある日、数式のハッシュ値を計算することによって効率よく数式検索をすることが出来るのではないかと考えた。
そこで、ある特定の条件を満たす多項式に対しては、変数に 1 か -1 を割り当ててその多項式を計算した時にその多項式が最小値を取るような変数の割り当ての総数を、その多項式のハッシュとすることにした。

しかし、ビッグブリッジ伯爵は他にも様々なアイディアを実装するので忙しい。
そこであなたは、ビッグブリッジ伯爵の代わりに数式のハッシュ値を計算するプログラムを書くことになった。

課題

30 変数以下の 2 次多項式 P が以下の制約のもとで与えられる。

• 多項式に現れる変数はA-Z, a-dのいずれか
• 多項式は必ず Σ 1 * x_i * x_j という形になっている
  • x_i, x_j はA-Z,a-dのどれかになっている
  • a * A + A * a => 2 * a * A や、 A * A + A * A => 2 * A * A のように整理したときに係数が 1 でない項があるようなものは与えらない
• 全ての変数はたかだか 4 回しか多項式に出現しない

各変数の値が -1, 1 のどちらかしかとらないとき、多項式が最小値を取るような変数の割り当て方の総数を求めよ。

配点

300

入力

入力は以下の形式で与えられる。

P

制約

入力 P は 1 文字の変数(A-Zとa-dのどれか)と掛け算を表す *、足し算を表す+のみで構成される。
P の中にA-Z,a-d,*,+以外の文字は出現しない。
課題に書かれている条件を満たす。

部分点

この問題には部分点が設定されている。この問題のテストケースのうち 30 点分は追加で以下の制約を満たす。

• 入力に出現する変数の種類が 20 種類以下

出力

最小値を取るような変数の割り当て方の総数 T を 1 行で出力せよ。

---

入力例1

a*A

出力例1

2

a=1 , A=-1 あるいは a=-1 , A=1 という 2 通りの割り当てが最小値を取る。

---

入力例2

a*A+b*b+c*a+b*a+A*b

出力例2

6

---

入力例3

A*C+A*V+A*W+B*M+B*R+B*c+C*J+C*T+D*M+D*Q+D*b+E*P+E*Y+E*c+F*Q+F*R+F*d+G*H+G*X+G*Y+H*J+H*L+I*K+I*L+I*M+J*Q+K*L+K*Z+N*T+N*Y+N*d+O*S+O*X+O*Z+P*U+P*V+R*U+S*V+S*b+T*d+U*a+W*X+W*b+Z*a+a*c

出力例3

30