I'm a Frayed Knot

Several colored threads lie on a table. Every thread has its own color, and its two ends appear somewhere in one straight line. Therefore each color appears exactly twice.

You must tie all threads into one large loop. At each step, choose two adjacent free ends and tie them together. If those two ends already belong to the same connected piece, tying them would close a separate loop, so that choice is forbidden unless it is the final tie that closes the single large loop.

Count how many different sequences of ties can complete the task.

The input contains several color patterns. Each pattern is a word of length at most 22 made of lowercase letters. Input ends with a line containing only #.

For each input pattern, print one line containing the number of valid tying sequences for that pattern. If a pattern is invalid because some character does not appear exactly twice, print 0 for that line.