//#define _GLIBCXX_DEBUG #include #define rep(i, n) for(int i=0; i; using vs = vector; using vi = vector; using vvi = vector; template using PQ = priority_queue; template using PQG = priority_queue, greater >; const int INF = 0xccccccc; const ll LINF = 0xcccccccccccccccLL; template inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);} template inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);} template istream &operator>>(istream &is, pair &p) { return is >> p.first >> p.second;} template ostream &operator<<(ostream &os, const pair &p) { return os << p.first << ' ' << p.second;} namespace fft { constexpr unsigned int modulo1 = 998244353; constexpr unsigned int modulo2 = 1000000007; constexpr long double PI = acos(-1); struct modint_base {}; template using is_modint = is_base_of; template using is_modint_t = enable_if_t::value>; template using is_complex = typename conditional>::value || is_same>::value, true_type, false_type>::type; //begin NTT template struct mint : modint_base { unsigned int x; static constexpr int mod() {return m;} static constexpr unsigned int umod() {return m;} mint():x(0) {} mint(int64_t x_) { int64_t v = int64_t(x_ % umod()); if(v < 0) v += umod(); x = (unsigned int)v; } static mint row(int v) { mint v_; v_.x = v; return v_; } mint operator-() const { return mint(-x);} mint& operator+=(const mint a) { if ((x += a.x) >= umod()) x -= umod(); return *this; } mint& operator-=(const mint a) { if ((x += umod()-a.x) >= umod()) x -= umod(); return *this; } mint& operator*=(const mint a) { uint64_t z = x; z *= a.x; x = (unsigned int)(z % umod()); return *this; } mint operator+(const mint a) const { return mint(*this) += a;} mint operator-(const mint a) const { return mint(*this) -= a;} mint operator*(const mint a) const { return mint(*this) *= a;} mint &operator++() { x++; if(x == umod()) x = 0; return *this; } mint &operator--() { if(x == 0) x = umod(); x--; return *this; } mint operator++(int) { mint result = *this; ++*this; return result; } mint operator--(int) { mint result = *this; --*this; return result; } mint pow(int64_t t) const { mint x_ = *this, r = 1; while(t) { if(t&1) r *= x_; x_ *= x_; t >>= 1; } return r; } mint inv() const { return pow(umod()-2);} mint& operator/=(const mint a) { return *this *= a.inv();} mint operator/(const mint a) {return mint(*this) /= a;} friend bool operator==(const mint &a, const mint &b) {return a.x == b.x;} friend bool operator!=(const mint &a, const mint &b) {return a.x != b.x;} }; constexpr int64_t safe_mod(int64_t x, int64_t m) { x %= m; if(x < 0) x += m; return x; } constexpr int64_t pow_mod_constexpr(int64_t x, int64_t n, int m) { if(m == 1) return 0; unsigned int _m = (unsigned int)(m); uint64_t r = 1; uint64_t y = safe_mod(x, m); while(n) { if(n&1) r = (r*y)%_m; y = (y*y)%_m; n >>= 1; } return r; } constexpr int primitive_root_constexpr(int m) { if(m == 2) return 1; if(m == 167772161) return 3; if(m == 469762049) return 3; if(m == 754974721) return 11; if(m == 998244353) return 3; int divs[20] = {}; divs[0] = 2; int cnt = 1; int x = (m-1)>>1; while(~x&1) x >>= 1; for(int i = 3; (int64_t)(i)*i <= x; i += 2) { if(x%i == 0) { divs[cnt++] = i; while(x%i == 0) x /= i; } } if(x > 1) divs[cnt++] = x; for(int g = 2;; g++) { bool ok = true; for(int i = 0; i < cnt; i++) { if(pow_mod_constexpr(g, (m-1)/divs[i], m) == 1) { ok = false; break; } } if(ok) return g; } } template constexpr int primitive_root = primitive_root_constexpr(m); constexpr pair inv_gcd(int64_t a, int64_t b) { a = safe_mod(a, b); if(a == 0) return {b, 0}; int64_t s = b, t = a; int64_t m0 = 0, m1 = 1; while(t) { int64_t u = s/t; s -= t*u; m0 -= m1*u; int64_t tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp; } if(m0 < 0) m0 += b/s; return {s, m0}; } int ceil_pow2(int n) { int x = 0; while((1U << x) < (unsigned int)(n)) x++; return x; } template* = nullptr> void butterfly(vector &ary) { static constexpr int g = primitive_root; int n = int(ary.size()); int h = ceil_pow2(n); static bool first = true; static mint sum_e[30]; if(first) { first = false; mint es[30], ies[30]; int cnt2 = __builtin_ctz(mint::mod()-1); mint e = mint(g).pow((mint::mod()-1)>>cnt2), ie = e.inv(); for(int i = cnt2; i >= 2; i--) { es[i-2] = e; ies[i-2] = ie; e *= e; ie *= ie; } mint now(1); for(int i = 0; i < cnt2-2; i++) { sum_e[i] = es[i] * now; now *= ies[i]; } } for(int ph = 1; ph <= h; ph++) { int w = 1<<(ph-1), p = 1<<(h-ph); mint now(1); for(int s = 0; s < w; s++) { int offset = s << (h-ph+1); for(int i = 0; i < p; i++) { mint l = ary[i+offset]; mint r = ary[i+offset+p] * now; ary[i+offset] = l+r; ary[i+offset+p] = l-r; } now *= sum_e[__builtin_ctz(~(unsigned int)(s))]; } } } template* = nullptr> void butterfly_inv(vector &ary) { static constexpr int g = primitive_root; int n = int(ary.size()); int h = ceil_pow2(n); static bool first = true; static mint sum_ie[30]; if(first) { first = false; mint es[30], ies[30]; int cnt2 = __builtin_ctz(mint::mod()-1); mint e = mint(g).pow((mint::mod()-1)>>cnt2), ie = e.inv(); for(int i = cnt2; i >= 2; i--) { es[i-2] = e; ies[i-2] = ie; e *= e; ie *= ie; } mint now(1); for(int i = 0; i < cnt2-2; i++) { sum_ie[i] = ies[i] * now; now *= es[i]; } } for(int ph = h; ph >= 1; ph--) { int w = 1<<(ph-1), p = 1<<(h-ph); mint inow(1); for(int s = 0; s < w; s++) { int offset = s<<(h-ph+1); for(int i = 0; i < p; i++) { mint l = ary[i+offset]; mint r = ary[i+offset+p]; ary[i+offset] = l+r; ary[i+offset+p] = (uint64_t)(mint::mod() + l.x - r.x) * inow.x; } inow *= sum_ie[__builtin_ctz(~(unsigned int)(s))]; } } } template* = nullptr> vector convolution(vector a, vector b) { int n = int(a.size()), m = int(b.size()); if(!n || !m) return {}; if(min(n, m) <= 60) { if(n < m) { swap(n, m); swap(a, b); } vector ans(n+m-1); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { ans[i+j] += a[i] * b[j]; } } return ans; } int z = 1<::value>* = nullptr> vector convolution(const vector &a, const vector &b) { int n = int(a.size()), m = int(b.size()); if(!n || !m) return {}; using Mint = mint; vector a2(n), b2(m); for(int i = 0; i < n; i++) { a2[i] = Mint(a[i]); } for(int i = 0; i < m; i++) { b2[i] = Mint(b[i]); } vector c2 = convolution(move(a2), move(b2)); vector c(n+m-1); for(int i = 0; i < n+m-1; i++) c[i] = c2[i].x; return c; } vector convolution_ll(const vector &a, vector &b) { int n = int(a.size()), m = int(b.size()); if(!n || !m) return {}; static constexpr uint64_t MOD1 = 754974721; // 2^24 static constexpr uint64_t MOD2 = 167772161; // 2^25 static constexpr uint64_t MOD3 = 469762049; // 2^26 static constexpr uint64_t M2M3 = MOD2 * MOD3; static constexpr uint64_t M1M3 = MOD1 * MOD3; static constexpr uint64_t M1M2 = MOD1 * MOD2; static constexpr uint64_t M1M2M3 = MOD1 * MOD2 * MOD3; static constexpr uint64_t i1 = inv_gcd(M2M3, MOD1).second; static constexpr uint64_t i2 = inv_gcd(M1M3, MOD2).second; static constexpr uint64_t i3 = inv_gcd(M1M2, MOD3).second; vector c1 = convolution(a, b); vector c2 = convolution(a, b); vector c3 = convolution(a, b); vector c(n+m-1); for(int i = 0; i < n+m-1; i++) { uint64_t x = 0; x += (c1[i] * i1) % MOD1 * M2M3; x += (c2[i] * i2) % MOD2 * M1M3; x += (c3[i] * i3) % MOD3 * M1M2; int64_t diff = c1[i] - safe_mod(int64_t(x), int64_t(MOD1)); if(diff < 0) diff += MOD1; static constexpr uint64_t offset[5] = {0, 0, M1M2M3, 2*M1M2M3, 3*M1M2M3}; x -= offset[diff%5]; c[i] = x; } return c; } //begin FFT template::value>* = nullptr> void butterfly(vector>& ary) { int n = int(ary.size()); int h = ceil_pow2(n); using Complex = complex; static bool first = true; static Complex sum_e[30]; if(first) { first = false; Complex now = 1.0; for(int i = 0; i < 28; i++) { Complex es = polar(Float(1.0), Float(PI)/(1<<(i+1))); sum_e[i] = es * now; now *= conj(es); } } for(int ph = 1; ph <= h; ph++) { int w = 1<<(ph-1), p = 1<<(h-ph); Complex now = Complex(1.0, 0); for(int s = 0; s < w; s++) { int offset = s<<(h-ph+1); for(int i = 0; i < p; i++) { Complex l = ary[i+offset]; Complex r = ary[i+offset+p] * now; ary[i+offset] = l+r; ary[i+offset+p] = l-r; } now *= sum_e[__builtin_ctz(~(unsigned int)(s))]; } } } template::value>* = nullptr> void butterfly_inv(vector> &ary) { int n = int(ary.size()); int h = ceil_pow2(n); using Complex = complex; static bool first = true; static Complex sum_ie[30]; if(first) { first = false; Complex now = 1.0; for(int i = 0; i < 28; i++) { Complex es = polar(Float(1.0), Float(PI)/(1<<(i+1))); sum_ie[i] = conj(es) * now; now *= es; } } for(int ph = h; ph >= 1; ph--) { int w = 1<<(ph-1), p = 1<<(h-ph); Complex inow = Complex(1.0, 0); for(int s = 0; s < w; s++) { int offset = s<<(h-ph+1); for(int i = 0; i < p; i++) { Complex l = ary[i+offset]; Complex r = ary[i+offset+p]; ary[i+offset] = l+r; ary[i+offset+p] = (l-r) * inow; } inow *= sum_ie[__builtin_ctz(~(unsigned int)(s))]; } } Complex in(1.0/n, 0); for(int i = 0; i < n; i++) ary[i] *= in; } template::value>* = nullptr> vector convolution(vector a, vector b) { int n = int(a.size()), m = int(b.size()); if(!n || !m) return {}; if(min(n, m) <= 60) { if(n < m) { swap(n, m); swap(a, b); } vector ans(n+m-1); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { ans[i+j] += a[i] * b[j]; } } return ans; } int z = 1<::value>* = nullptr> vector convolution(vector &a, vector &b) { int n = int(a.size()), m = int(b.size()); if(!n || !m) return {}; using Complex = complex; vector a2(n), b2(m); for(int i = 0; i < n; i++) a2[i] = Complex(a[i], 0); for(int i = 0; i < m; i++) b2[i] = Complex(b[i], 0); vector c2 = convolution(move(a2), move(b2)); vector c(n+m-1); for(int i = 0; i < n+m-1; i++) c[i] = c2[i].real(); return c; } //modulo1 998244353 //modulo2 1000000007 //vector> convolution(vector>, vector>) //vector convolution(vector&, vector&) ##is_integral::value == true //vector convolution_ll(vector&, vector&) //vector convolution(vector, vector) //vector convolution(vector&, vector&) } // namespace fft struct combination { using Mint = fft::mint; vector frac, ifrac; combination(int n):frac(n+1), ifrac(n+1) { frac[0] = 1; for (int i = 1; i <= n; ++i) frac[i] = frac[i-1]*i; ifrac[n] = frac[n].inv(); for (int i = n; i >= 1; --i) ifrac[i-1] = ifrac[i]*i; } Mint operator()(int n, int k) { if (k < 0 || k > n) return 0; return frac[n]*ifrac[k]*ifrac[n-k]; } } c(1000000); #define AL 26 //head string s; int cnt[AL]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> s; rep(i, s.size()) cnt[s[i]-'a']++; vector> ans(1, 1); sort(cnt, cnt+AL); vector> now; rep(i, AL) { if(!cnt[i]) continue; rep(j, ans.size()) { ans[j] *= c.ifrac[j]; } while(now.size() < cnt[i]+1) now.emplace_back(c.ifrac[now.size()]); ans = fft::convolution(ans, now); rep(j, ans.size()) ans[j] *= c.frac[j]; } cout << accumulate(ans.begin()+1, ans.end(), fft::mint()).x << endl; }