Pyramid DFS Reconstruction

An ancient pyramid is known to have a tree‐like internal structure with a unique entrance (the root) and several rooms (nodes). Each room is painted in one of several colors. A specially designed robot enters the pyramid through the entrance and performs a depth-first search (DFS). Every time the robot enters a room, whether for the first time or when returning from a child room, it records the room's color. When the robot finally exits, it obtains a sequence of colors.

For a tree (pyramid) with n nodes the DFS works as follows:

Algorithm:
1. Enter the root and record its color A.
2. For each child of the current node (in order):
    a. Recursively perform DFS on the child (when entering the child, record its color and all subsequent entries in its subtree).
    b. When the child subtree is completely traversed, backtrack to the parent and record the parent's color A.

Thus, the DFS sequence for a node with color A and k children is structured as follows:

where each T_i is the DFS sequence of the i-th child (and is nonempty). Notice that a leaf node has a DFS sequence consisting of a single element.

Given a color sequence S produced by the robot, your task is to calculate the number of different pyramid structures (i.e. ordered rooted trees together with a valid assignment of colors to rooms) that would yield exactly that DFS sequence. Since the answer may be very large, output it modulo $$10^9$$.

Note: If the sequence length does not allow a valid DFS traversal (recall that a DFS sequence of a tree with n nodes has length 2n-1), then the answer is 0.

inputFormat

The input consists of a single line containing a non-empty string S representing the sequence of colors recorded by the robot. Each character in S denotes a color. It is guaranteed that S contains only visible ASCII characters and has length at most 200.

outputFormat

Output a single integer, the number of possible pyramid structures that yield the given DFS sequence, modulo $$10^9$$.

sample

a

1