問題文

0、1 からなる文字列 $S$ が与えられます。 以下の操作を $0$ 回以上繰り返して作ることのできる文字列としてありうるものの個数を求めてください。

• 以下の条件 (1), (2), (3) を満たす $S$ の２つの空でない連続部分列 $t$、$u$ を選び、$S$ 中での位置を交換する。
  • (1): $t$ と $u$ は、重なりの無いように取り出す。 即ち、$t$ が $S$ の $L_t$〜$R_t$ 文字目であり、$u$ が $S$ の $L_u$〜$R_u$ 文字目であるとすると、 $L_t\le R_t < L_u\le R_u$ が成り立つようにする。
  • (2): $t$ に含まれる 0 の数は、$u$ に含まれる 0 の数に等しい。
  • (3): $t$ に含まれる 1 の数は、$u$ に含まれる 1 の数に等しい。

入力

$S$

【制約】

• $S$ は 0、1 からなる長さ $1$ 以上 $60$ 以下の文字列

出力

操作を $0$ 回以上行ってできる可能性のある文字列の個数を 1 行に出力せよ。

サンプル

001010

2

10

1

010101

3