Aristocracy

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define X real()
#define Y imag()

map<char,int> trie[1110101];
int newest;
const ll M = 1000000007;
ll fac[101010];
ll ifac[101010];

ll mpow(ll a, ll e) {
    ll res=1;
    while (e) {
        if (e%2) {
            res*=a;
            res%=M;
        }
        a*=a;
        a%=M;
        e/=2;
    }
    return res;
}

ll inv(ll a) {
    return mpow(a,M-2);
}

void process(string s) {
    int node = 0;
    for (char c : s) {
        if (trie[node].count(c)==0) trie[node][c] = ++newest;
        node = trie[node][c];
    }
    trie[node]['*']++;
}

int main() {
    int n;
    cin>>n;
    newest=0;
    for (int i=0;i<n;i++) {
        string s;
        cin>>s;
        process(s);
        int k;cin>>k;
    }

    fac[0]=1;
    ifac[0]=1;
    for (int i=1;i<=n;i++) fac[i]=(i*fac[i-1])%M;
    for (int i=1;i<=n;i++) ifac[i]=(inv(i)*ifac[i-1])%M;

    ll res=fac[n];
    for (int i=0;i<=newest;i++) {
        res*=ifac[trie[i]['*']];
        res%=M;
    }

    cout<<res<<"\n";

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED