#line 2 "/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp" #define _CRT_SECURE_NO_WARNINGS #pragma target("avx2") #pragma optimize("O3") #pragma optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(int i=0;i<(n);i++) #define REP(i,n) for(int i=1;i<=(n);i++) #define all(V) V.begin(),V.end() typedef long long lint; typedef unsigned long long ulint; typedef std::pair P; typedef std::pair LP; constexpr int INF = INT_MAX/2; constexpr lint LINF = LLONG_MAX/2; constexpr double eps = DBL_EPSILON; constexpr double PI=3.141592653589793238462643383279; template class prique :public std::priority_queue, std::greater> {}; template inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; } template inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; } inline lint gcd(lint a, lint b) { while (b) { lint c = a; a = b; b = c % b; } return a; } inline lint lcm(lint a, lint b) { return a / gcd(a, b) * b; } bool isprime(lint n) { if (n == 1)return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0)return false; } return true; } template T mypow(T a, lint b) { T res(1); while(b){ if(b&1)res*=a; a*=a; b>>=1; } return res; } lint modpow(lint a, lint b, lint m) { lint res(1); while(b){ if(b&1){ res*=a;res%=m; } a*=a;a%=m; b>>=1; } return res; } template void printArray(std::vector& vec) { rep(i, vec.size()){ std::cout << vec[i]; std::cout<<(i==(int)vec.size()-1?"\n":" "); } } template void printArray(T l, T r) { T rprev = std::prev(r); for (T i = l; i != rprev; i++) { std::cout << *i << " "; } std::cout << *rprev << std::endl; } LP extGcd(lint a,lint b) { if(b==0)return {1,0}; LP s=extGcd(b,a%b); std::swap(s.first,s.second); s.second-=a/b*s.first; return s; } LP ChineseRem(const lint& b1,const lint& m1,const lint& b2,const lint& m2) { lint p=extGcd(m1,m2).first; lint tmp=(b2-b1)*p%m2; lint r=(b1+m1*tmp+m1*m2)%(m1*m2); return std::make_pair(r,m1*m2); } template inline constexpr decltype(auto) lambda_fix(F&& f){ return [f=std::forward(f)](auto&&... args){ return f(f,std::forward(args)...); }; } #line 3 "/Users/kaage/Desktop/ProgrammingWorkspace/library/algebraic/ModInt.hpp" class ModInt { lint value; public: static unsigned int modulo; ModInt() : value(0) {} template ModInt(T value = 0) : value(value) { if (value < 0)value = -(lint)(-value % modulo) + modulo; this->value = value % modulo; } static inline void setMod(const unsigned int& mod){modulo=mod;} inline ModInt inv()const{return mypow(*this,modulo-2);} inline operator int()const { return value; } inline ModInt& operator+=(const ModInt& x) { value += x.value; if (value >= modulo)value -= modulo; return *this; } inline ModInt& operator++() { if (value == modulo - 1)value = 0; else value++; return *this; } inline ModInt operator-()const { return ModInt(0) -= *this; } inline ModInt& operator-=(const ModInt& x) { value -= x.value; if (value < 0)value += modulo; return *this; } inline ModInt& operator--() { if (value == 0)value = modulo - 1; else value--; return *this; } inline ModInt& operator*=(const ModInt& x) { value = value * x.value % modulo; return *this; } inline ModInt& operator/=(const ModInt& rhs) { return *this*=rhs.inv(); } template ModInt operator+(const T& rhs)const { return ModInt(*this) += rhs; } template ModInt& operator+=(const T& rhs) { return operator+=(ModInt(rhs)); } template ModInt operator-(const T& rhs)const { return ModInt(*this) -= rhs; } template ModInt& operator-=(const T& rhs) { return operator-=(ModInt(rhs)); } template ModInt operator*(const T& rhs)const { return ModInt(*this) *= rhs; } template ModInt& operator*=(const T& rhs) { return operator*=(ModInt(rhs)); } template ModInt operator/(const T& rhs)const { return ModInt(*this) /= rhs; } template ModInt& operator/=(const T& rhs) { return operator/=(ModInt(rhs)); } }; unsigned int ModInt::modulo=1000000007; std::istream& operator>>(std::istream& ist, ModInt& x) { lint a; ist >> a; x = a; return ist; } #line 4 "/Users/kaage/Desktop/ProgrammingWorkspace/library/algebraic/NumberTheoreticTransform.hpp" //1012924417,5,2^21 //924844033,5,2^21 //998244353,3,2^23 //1224736769,3,2^24 //167772161,3,2^25 //469762049,3,2^26 class NumberTheoreticTransform{ private: static void ntt(std::vector& a){ int sz=a.size(); if(sz==1)return; ModInt root=ModInt::modulo==924844033||ModInt::modulo==1012924417?5:3; if(inverse)root=mypow(root,ModInt::modulo-1-(ModInt::modulo-1)/sz); else root=mypow(root,(ModInt::modulo-1)/sz); std::vector b(sz),roots((sz>>1)+1,1); rep(i,sz>>1)roots[i+1]=roots[i]*root; for(int i=sz>>1,w=1;w>=1,w<<=1){ for(int j=0;j>1)]; b[k+((w*j)<<1)+w]=roots[w*j]*(a[k+w*j]-a[k+w*j+(sz>>1)]); } } std::swap(a,b); } } public: static bool inverse; template static std::vector multiply(std::vector f, std::vector g, const unsigned int& mod) { unsigned int beforeMod=ModInt::modulo; ModInt::setMod(mod); if(f.size() nf, ng; int sz=1; while (sz static std::vector multiply_plain(std::vector f,std::vector g){ const unsigned int mod1=998244353,mod2=1224736769; std::vector mul1=multiply(f,g,mod1); std::vector mul2=multiply(f,g,mod2); std::vector res(mul1.size()); rep(i,mul1.size())res[i]=ChineseRem(mul1[i],mod1,mul2[i],mod2).first; return res; } }; bool NumberTheoreticTransform::inverse=false; #line 4 "main.cpp" std::string s; int a[26]; ModInt fact[300010],inv[300010]; int main(){ ModInt::setMod(998244353); std::cin>>s; rep(i,s.size())a[s[i]-'a']++; std::sort(a,a+26); fact[0]=1; REP(i,s.size())fact[i]=fact[i-1]*i; inv[s.size()]=ModInt(1)/fact[s.size()]; for(int i=s.size()-1;i>=0;i--)inv[i]=inv[i+1]*(i+1); std::vector ans={1}; rep(i,26){ if(!a[i])continue; std::vector vec(a[i]+1,1); rep(j,ans.size())ans[j]*=inv[j]; rep(j,vec.size())vec[j]*=inv[j]; ans=NumberTheoreticTransform::multiply(ans,vec,ModInt::modulo); while(!ans.back())ans.pop_back(); rep(j,ans.size())ans[j]*=fact[j]; } ModInt res=0; REP(i,ans.size()-1)res+=ans[i]; std::cout<