/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
文字列 S が与えられます。S の空でない、連続するとは限らない部分列を並び替えて得られる文字列は何種類ありますか？
答えは非常に大きくなる場合があるので、998244353 で割ったあまりを出力してください。
制約
- S は英小文字のみからなる長さ 1 以上 5000 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S の部分列を並び替えて得られる文字列の種類数を 998244353 で割ったあまりを出力せよ。
入力例 1
aab
出力例 1
8
S の部分列を並び替えて得られる文字列は、a, b, aa, ab, ba, aab, aba, baa の 8 種類です。
入力例 2
aaa
出力例 2
3
入力例 3
abcdefghijklmnopqrstuvwxyz
出力例 3
149621752
998244353 で割ったあまりを出力することに注意してください。
Score : 500 points
Problem Statement
Given is a string S. How many different strings can be obtained as a permutation of a non-empty, not necessarily contiguous subsequence of S?
Since the count can be enormous, print it modulo 998244353.
Constraints
- S is a string of length 1 and 5000 (inclusive) consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
Print the number of different strings that can be obtained as a permutation of a subsequence of S, modulo 998244353.
Sample Input 1
aab
Sample Output 1
8
There are 8 different strings that can be obtained as a permutation of a subsequence of S: a, b, aa, ab, ba, aab, aba, baa.
Sample Input 2
aaa
Sample Output 2
3
Sample Input 3
abcdefghijklmnopqrstuvwxyz
Sample Output 3
149621752
Be sure to print the count modulo 998244353.