레인보우 문자열
시간 제한1초메모리 제한512 MB
문자열의 부분수열 중 같은 글자가 겹치지 않는 것의 개수를 위치로 구분해 세고, 11092019로 나눈 나머지를 구한다.
문제
어떤 문자열에 등장하는 모든 문자가 서로 다르면 그 문자열을 레인보우 문자열이라고 하자. 빈 문자열도 레인보우 문자열이다.
소문자로 이루어진 문자열이 주어진다. 이 문자열의 부분 수열 중 레인보우 문자열인 것의 개수를 구하라. 두 부분 수열은, 특정 위치의 문자가 한쪽 부분 수열에는 포함되고 다른 쪽에는 포함되지 않으면 서로 다른 부분 수열이다. 따라서 서로 다른 두 부분 수열이 같은 문자열이 될 수도 있다.
예를 들어 문자열 aab를 보자. 다음 여섯 개의 부분 수열만이 aab의 레인보우 문자열이다.
aab aab aab aab aab <empty>
답이 클 수 있으므로 답을 11092019로 나눈 나머지를 출력한다.
입력
한 줄에 문자열 s가 주어진다. (1 ≤ |s| ≤ 105) s는 소문자로만 이루어져 있다.
출력
s의 부분 수열 중 레인보우 문자열인 것의 개수를 한 줄에 출력한다.