A jeweler lays out a straight strand of colored beads, one bead per position. Beads of the same color are identical and indistinguishable from one another. Given the multiset of bead colors, count how many visually distinct arrangements of all the beads in a row are possible.

Two arrangements are the same only if every position shows the same color in both.

Input format

A single line: a string of 1 to 8 lowercase English letters, where each letter is the color of one bead.

Output format

A single integer: the number of distinct arrangements of all the beads in a row.

Constraints

• 1 <= number of beads <= 8
• Each bead color is a lowercase English letter ('a'-'z').

aab

3

abc

6