Use extended Euclidian Algorithm to evaluate the faction mod p
Code\n\nuse std::collections::HashMap;\n\nconst BIG:i64 = 1_000_000_007;\n\n// modular inverse\nfn inv(k: i64) -> i64 {\n    egcd(k, BIG).1.rem_euclid(BIG)\n}\n
# Code\n```\nuse std::collections::HashMap;\n\nconst BIG:i64 = 1_000_000_007;\n\n// modular inverse\nfn inv(k: i64) -> i64 {\n    egcd(k, BIG).1.rem_euclid(BIG)\n}\n\nfn egcd(x: i64, y: i64) -> (i64, i64, i64) {\n    match y {\n        0 => (x, 1, 0),\n        _ => {let k = x/y; \n              let r = x.rem_euclid(y);\n              let (d, a, b) = egcd(y, r);\n              (d, b, a-k*b)\n              }\n    }\n}\n\n\nfn cc(w:&str) -> i64 {\n    let mut h : HashMap<char, i64> = HashMap::new();\n    let mut a = 1;\n    let mut b = 1;\n    for (i,c) in w.chars().enumerate() {\n        *h.entry(c).or_default() += 1;\n        a = a * (i as i64+1) % BIG;\n        b = b * h[&c] % BIG\n    }\n    a * inv(b) % BIG \n}\n\nimpl Solution {\n    pub fn count_anagrams(s: String) -> i32 {\n        s.split_ascii_whitespace().map(cc).fold(1,|acc,x|(acc*x)%BIG) as _\n    }\n}\n```
['Rust']