시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 512 MB73545176.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.

예제 입력 1

aab

예제 출력 1

6

예제 입력 2

icpcprogrammingcontest

예제 출력 2

209952