Giải bài trực tuyến

Trailing zeroes

Given a string of N lowercase characters ('a'->'z') (N ≤ 10000). Consider the different permutations of this string. For example, with the string abbb we have four permutations:

abbb, babb, bbab, bbba

Your task is to find the number of trailing zeroes in the number of different permutations of the given string.

Input

A single line: the string S.

Output

A single number: the number of trailing zeroes.

Example

Input
babb

Output
0