시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 512 MB | 73 | 54 | 51 | 76.119% |
Define a Rainbow String as a string where every letter in the string is distinct. The empty string is a Rainbow String.
Given a string of lower-case letters, compute the number of different subsequences which are Rainbow Strings. Two subsequences are different if letter at a specific position is included in one subsequence but not the other. Thus, two different subsequences may result in the same string.
For example, consider the string aab
. The following six subsequences (in bold and underlined) are the only Rainbow Strings in aab
:
aab aab aab aab aab <empty>
The answer may be large, so output the answer modulo 11092019.
The single line of input contains a string s (1 ≤ |s| ≤ 105) which consists only of lower-case letters.
Output a single integer, which is the number of subsequences of s which are Rainbow Strings.
aab
6
icpcprogrammingcontest
209952
ICPC > Regionals > North America > Southeast USA Regional > 2019 Southeast USA Regional Programming Contest > Division 2 J번
ICPC > Regionals > North America > Pacific Northwest Regional > 2019 ICPC Pacific Northwest Region > Division 1 E번
ICPC > Regionals > North America > Pacific Northwest Regional > 2019 ICPC Pacific Northwest Region > Division 2 R번