Number of Trees

There is a rooted ordered tree. Each vertex has one uppercase English letter written on it, and the same letter may appear on multiple vertices.

The traversal starts at the root. Whenever the traversal arrives at a vertex, it writes that vertex's letter to the path. Then it visits the unvisited children of that vertex from left to right, one at a time. After finishing one child and returning to its parent, the parent's letter is written again. Therefore, a vertex with children may appear in the path several times.

Given an uppercase path string, count how many rooted ordered trees produce exactly that path. Trees with different left-to-right child order are counted as different trees.

The first line contains the path string. It consists only of uppercase English letters, and its length is at most 300.

Print the number of possible trees modulo 1,000,000,000.