/** * author: otera **/ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long typedef long long ll; typedef unsigned long long ul; typedef unsigned int ui; typedef long double ld; const int inf=1e9+7; const ll INF=1LL<<60 ; const ll mod=1e9+7 ; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef complex Point; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair P; typedef pair LDP; typedef pair LP; #define fr first #define sc second #define all(c) c.begin(),c.end() #define pb push_back #define debug(x) cerr << #x << " = " << (x) << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } long long modinv(long long a, long long mod) { long long b = mod, u = 1, v = 0; while (b) { long long t = a/b; a -= t*b; swap(a, b); u -= t*v; swap(u, v); } u %= mod; if (u < 0) u += mod; return u; } template struct ntt{ inline void add(int &a, int b) { a += b; if(a >= md) a -= md; } inline void sub(int &a, int b) { a -= b; if(a < 0) a += md; } inline int mul(int a, int b) { return (int)((ll)a*b%md); } inline int power(int a, long long b) { int res = 1; while (b > 0) { if (b & 1) res = mul(res, a); a = mul(a, a); b >>= 1; } return res; } inline int inv(int a) { a %= md; if (a < 0) a += md; int b = md, u = 0, v = 1; while (a) { int t = b / a; b -= t * a; swap(a, b); u -= t * v; swap(u, v); } assert(b == 1); if (u < 0) u += md; return u; } int max_base, root; vector dw, idw; ntt() { int tmp = md - 1; max_base = 0; while (tmp % 2 == 0) { tmp /= 2; max_base++; } root = 2; while (power(root, (md-1)>>1) == 1) root++; dw.resize(max_base); idw.resize(max_base); rep(i, max_base){ sub(dw[i], power(root, (md-1) >> (i+2))); idw[i] = inv(dw[i]); } } void fft(vector &a, bool inv) { const int n = a.size(); assert((n & (n - 1)) == 0); assert(__builtin_ctz(n) <= max_base); if(!inv){ for(int m=n;m>>=1;){ int w = 1; for(int s=0,k=0; s=y?x-y:x+md-y); a[i] = (x+y>=md?x+y-md:x+y); } w = mul(w, dw[__builtin_ctz(++k)]); } } } else{ for(int m=1;m=y?x-y:x+md-y); a[j] = mul(a[j], w); a[i] = (x+y>=md?x+y-md:x+y); } w = mul(w, idw[__builtin_ctz(++k)]); } } } } vector multiply(vector a, vector b, int eq = 0) { int need = a.size() + b.size() - 1; int nbase = 0; while ((1 << nbase) < need) nbase++; int sz = 1 << nbase; a.resize(sz); b.resize(sz); fft(a, 0); if (eq) b = a; else fft(b, 0); int inv_sz = inv(sz); for (int i = 0; i < sz; i++) { a[i] = mul(mul(a[i], b[i]), inv_sz); } fft(a, 1); a.resize(need); return a; } vector square(vector a) { return multiply(a, a, 1); } }; const int MOD = 998244353; ntt NTT; void solve() { string s; cin >> s; int n = (int)s.size(); vector cnt(26, 0); rep(i, n) { cnt[s[i] - 'a'] ++; } vector a(1, 1LL); sort(all(cnt)); rep(i, 26) { vector b(cnt[i] + 1, 1LL); ll cur = 1LL; rep(j, cnt[i] + 1) { if(j != 0) cur *= modinv(j, MOD); cur %= MOD; b[j] = cur; } a = NTT.multiply(a, b); } ll cur = 1; ll ans = 0; for(ll k = 1; k <= n; ++ k) { cur *= k; cur %= MOD; ans += (a[k] * cur) % MOD; if(ans >= MOD) ans -= MOD; } cout << ans << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); //cout << fixed << setprecision(10); //int t; cin >> t; rep(i, t)solve(); solve(); return 0; }