시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 32 19 17 56.667%

문제

a, b, c로만 이루어진 문자열 S가 주어졌을 때, S의 부분 수열 중에서 aibjck의 형태로 이루어진 것의 개수를 구하는 프로그램을 작성하시오. 이 때, i ≥ 1, j ≥ 1, k ≥ 1을 만족해야 한다.

aibjck는 a가 i개 나오고, 이어서 b가 j개, c가 k개 연속해서 나오는 문자열이다. 예를 들어, a2b3c1은 "aabbbc"를 나타내며, a3b1c6은 "aaabcccccc"를 나타낸다.

입력

첫째 줄에 a, b, c로만 이루어진 문자열 S가 주어진다. S의 길이는 1,000,000을 넘지 않는다.

출력

첫째 줄에 S의 부분 수열 중에서 aibjck 형태로 이루어진 것의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

abc

예제 출력 1

1

예제 입력 2

abcc

예제 출력 2

3

예제 입력 3

abbcc

예제 출력 3

9

예제 입력 4

aabbcc

예제 출력 4

27

예제 입력 5

abbccc

예제 출력 5

21

예제 입력 6

abbcccabc

예제 출력 6

51

예제 입력 7

abcabcabcabc

예제 출력 7

111

예제 입력 8

cba

예제 출력 8

0

예제 입력 9

aaaaabbbbbccccc

예제 출력 9

29791

출처