#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; class nComb { std::vector> impl_; public: // O(maxN^2) nComb(int maxN, int Mod=1) { impl_.resize(maxN+1, std::vector(maxN+1, 0)); for (int n = 0; n < maxN; ++n) { impl_[n][0] = 1; for (int r = 0; r <= n; ++r) { impl_[n+1][r+1] = (impl_[n][r+1]+impl_[n][r]); if (Mod > 1) impl_[n+1][r+1] %= Mod; } } } long long operator()(int n, int r) { return impl_[n][r]; } }; class SwapStringMed { public: void solve(void) { string S; cin>>S; const int Mod = 573; int N = S.size(); map cnt; for (auto c : S) { cnt.emplace(c,0); ++cnt[c]; } // 隣同士の swap だけ並び替えを表現できる // N!/(a!b!...c!) を計算すればよいだけ // mod 込みの 1/a! 計算をする必要がある。 // // nCr = n!/(r!(n-r)!) より // N!/(a!b!) = N!/(a!(N-a)!) * (N-a!)/b! // = NCa * (N-a)Cb * (N-a-b)! // // と nCr で表現できるのでこれを計算すればよい nComb nCr(N, Mod); ll count = 1; for (auto c : cnt) { int a = c.second; (count *= nCr(N,a)) %= Mod; N -= a; } // (a+b+...+c = N より最後の (N-a-b)! = 0! = 1 となる) // 最初の文字列はのぞく cout<<(count-1)<solve(); delete obj; return 0; } #endif