Shared code

// s  = aabac
// s1 = aabac
// s2 = baaac
// s3 = bacaa
// s4 = cabaa
// ...
// s20 = ... 

// Hướng tiếp cận đầu tiên (dễ nghĩ hơn): dùng công thức tổ hợp nCk   

// s = aabac  

// cnt('a') = 3   
// cnt('b') = 1  
// cnt('c') = 1   

// và tổng cộng có 5 vị trí  

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;  

// Nhập vào n, k. In ra nCk mod 10^9 + 7.  

// nCk = n! / [(n - k)! * k!]

const int N = 1e6 + 5;  
const int MOD = 1e9 + 7;  

ll fact[N], inv_fact[N];  

ll binpow(ll a, ll b) {
	ll ans = 1;  
	for (; b > 0; b >>= 1) {
		if (b & 1) ans = ans * a % MOD;    
		a = a * a % MOD; 
	}
	return ans; 
}

ll inv(int x) {
	return binpow(x, MOD - 2);   
}

void precompute() {
	fact[0] = 1;  
	// i! = (i - 1)! * i  
	for (int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;   

	inv_fact[N - 1] = inv(fact[N - 1]);   
	for (int i = N - 2; i >= 0; i--) inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;   
}

ll nCk(int n, int k) { // n >= k 
	if (n < k) return 0;   
	return fact[n] * inv_fact[n - k] % MOD * inv_fact[k] % MOD;  
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);  
	string s; 
	cin >> s;   
	int n = s.size();   

	vector<int> cnt(26, 0);   
	for (int i = 0; i < n; i++) cnt[s[i] - 'a']++;   

	precompute(); // O(n) 
	
	ll ans = 1;  
	for (int c = 0; c <= 25; c++) {
		ans = ans * nCk(n, cnt[c]) % MOD;   
		n -= cnt[c]; 
	}

	cout << ans << '\n'; 
}