18007번 - Rainbow Strings 다국어

문제

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| ≤ 10⁵) which consists only of lower-case letters.

출력

Output a single integer, which is the number of subsequences of s which are Rainbow Strings.

제한

힌트