Problem Description

Although exploring pyramids is a very old-fashioned plot, a team of explorers still arrived at the foot of a pyramid.

After years of research, scientists have already learned something about the internal structure of this pyramid.

First, the pyramid consists of several rooms, and there are passages connecting rooms.

If we regard rooms as nodes and passages as edges, then the whole pyramid forms a rooted tree. The subtrees of each node are ordered, and the pyramid has exactly one entrance that leads to the root of the tree.

Also, the wall of each room is painted in exactly one color chosen from several possible colors.

The explorers want to further understand the structure of the pyramid, so they use a specially designed robot.

The robot enters the pyramid from the entrance, and then performs a depth-first traversal of the pyramid.

Every time the robot enters a room (whether it is the first time or when returning), it records the color of that room.

Finally, the robot exits the pyramid from the entrance.

Obviously, the robot will visit every room at least once, and will traverse each passage exactly twice (once in each direction). Then, the robot obtains a color sequence.

However, the explorers found that this color sequence cannot uniquely determine the structure of the pyramid.

Now they want you to help them compute: for a given color sequence, how many different possible structures could produce this sequence.

Since the result may be very large, you only need to output the value of the answer modulo $10^9$.

Input Format

The input consists of only one line, containing a string $S$ with length at most $300$, representing the color sequence recorded by the robot.

Output Format

Output one integer representing the answer.

ABABABA

5

Hint

Translated by ChatGPT 5