---
# System prepended metadata

title: CSES Creating Strings II

---

```java=
static int MOD = 1000000007;
 
    static long pre[] = new long[1000007];
    static long inv[] = new long[1000007];
    static long prei[] = new long[1000007];
 
    public static void build(int n) {
        pre[1] = pre[0] = 1;
        inv[1] = inv[0] = 1;
        prei[1] = prei[0] = 1;
 
        for (int i = 2; i <= n; i++) {
            pre[i] = pre[i - 1] * i % MOD;
            inv[i] = (MOD - MOD / i * inv[MOD % i] % MOD) % MOD;
            prei[i] = prei[i - 1] * inv[i] % MOD;
        }
    }
 
    public static long C(int n, int k){
        return pre[n] * prei[k] % MOD * prei[n - k]% MOD;
    }
 
    public static void main(String [] args) throws IOException {
        Reader r = new Reader();
        build(1000005);
 
        while(r.hasNext()){
            String str = r.next();
            int n = str.length();
            Map<Character, Integer> map = new HashMap<>();
 
            for(int i = 0; i < n; i ++){
                Character ch = str.charAt(i);
                map.put(ch, map.getOrDefault(ch, 0) + 1);
            }
 
            int total = n;
            long output = 1L;
            for(int val : map.values()){
                output =  (output * C(total, val)) % MOD;
                total -= val;
            }
 
            out.println(output% MOD);
            out.flush();
        }
 
    }
 
}
```