트리의 개수

루트가 있는 순서 있는 트리가 있다. 각 정점에는 알파벳 대문자 하나가 적혀 있으며, 같은 문자가 여러 정점에 적혀 있을 수 있다.

탐색은 루트에서 시작한다. 어떤 정점에 도착하면 그 정점의 문자를 경로에 적고, 아직 방문하지 않은 자식들을 왼쪽에서 오른쪽 순서로 하나씩 탐색한다. 자식 하나의 탐색이 끝나 부모 정점으로 돌아올 때마다 부모 정점의 문자도 다시 경로에 적는다. 따라서 자식이 있는 정점은 경로에 여러 번 나타날 수 있다.

대문자로 이루어진 경로 문자열이 주어졌을 때, 이 탐색으로 정확히 그 경로가 만들어지는 트리의 개수를 구하라. 자식의 왼쪽-오른쪽 순서가 다르면 서로 다른 트리로 센다.

첫째 줄에 경로 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 300 이하이다.

가능한 트리의 개수를 1,000,000,000으로 나눈 나머지를 출력한다.