$1$ から $34$ までの数が書かれたカードが十分にたくさんある。その中から何枚かを一列に並べ、書かれた数を順番に書き写した。例えば、カードが以下のように並んでいるとき、数を順番に書き写すと $27123$ になる。

27 | 1 | 23

後で、書き写したものに合うようにカードを再び並べようとすると、並べ方が複数ある場合があることが分かった。

例えば、$27123$ には以下のように異なる六つの並べ方がある。

2 | 7 | 1 | 2 | 3
27 | 1 | 2 | 3
2 | 7 | 12 | 3
2 | 7 | 1 | 23
27 | 12 | 3
27 | 1 | 23

カードの数を順番に書き写したものが与えられたとき、上のように逆にカードの並びを求めたい。可能なカードの並べ方が全部で何通りあるかを求めるプログラムを作成せよ。

入力

最初の行に、カードの数を順番に書き写したものが与えられる。これは長さが $40$ 以下の数字列である。

出力

可能なカードの並べ方の数を出力せよ。

入出力例

入力 1

27123

出力 1

6

入力 2

77777777777777777777

出力 2

1