AT_abc234_f [ABC234F] Reordering

题目描述

给定一个字符串 $S$。将 $S$ 的非空、不一定连续的子序列重新排列后可以得到多少种不同的字符串？

由于答案可能非常大，请输出其除以 $998244353$ 的余数。

输入格式

输入为以下格式，从标准输入读取。

$S$

输出格式

输出将 $S$ 的子序列重新排列后可以得到的不同字符串的种类数，结果对 $998244353$ 取模。

样例 1

输入

aab

输出

8

样例 2

输入

aaa

输出

3

样例 3

输入

abcdefghijklmnopqrstuvwxyz

输出

149621752

说明/提示

限制条件

• $S$ 只包含小写英文字母，长度为 $1$ 到 $5000$。

样例解释 1

将 $S$ 的子序列重新排列后可以得到的字符串有：a、b、aa、ab、ba、aab、aba、baa，共 $8$ 种。

样例解释 3

请注意，输出时需要对 $998244353$ 取模。

由 ChatGPT 4.1 翻译