13906번 - 대문자

소문자로만 이루어진 문장이 주어졌을 때, 다음과 같은 과정을 거쳐 대문자로만 이루어진 문장으로 바꾸려 한다.

1. 임의의 문자들을 제거한다. 제거할 수 있는 문자의 개수에는 제한이 없다. 제거할 문자들이 인접하지 않아도 된다. 문자를 하나도 제거하지 않는 것도 가능하다.
2. 인접한 세 개의 동일한 문자를 하나의 대문자로 바꾼다.

bbcccaabbba라는 문장이 주어진 경우 다음과 같은 5가지 문장을 만들 수 있다.

1. aaa만 남기고 다른 문자를 모두 제거하여, A로 바꾼다.
2. bbb만 남겨 B로 바꾼다.
3. ccc만 남겨 C로 바꾼다.
4. cccaaa만 남겨 CA로 바꾼다.
5. cccbbb만 남겨 CB로 바꾼다.

 소문자만 이루어진 문장이 주어졌을 때, 만들 수 있는 대문자로만 이루어진 문장의 수를 구하시오.

소문자로만 이루어진 문자열이 주어진다. 길이는 1 이상 1,000 이하이다.

만들 수 있는 대문자로만 이루어진 문장의 수를 1,000,000,007로 나눈 나머지를 출력한다.