Rust Module Division Using Fermat's Little Theorem
Intuition\n Describe your first thoughts on how to solve this problem. \n1) The number of ways of counstructing the solution is the multiplication of the number
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1) The number of ways of counstructing the solution is the multiplication of the number of ways of constructing each unique word.\n2) Assume f_1, f_2, ,, f_k are frequencies of distinct characters in a word, where f_1 + f_2 + ... + f_k = n. The number of ways to construct different anagram words is n! / (f_1! * f_2! * .. * f_k!).\n3) Fermat\'s Little Theorem states: for any a < p (1000000007, which is a prime), a ^ ( p - 1) == 1 (mod p).\n4) For any b (1 <= b <= p - 1) & a with b % a == 0, (b / a) % mod p == (b * a ^ (p - 2)) % mod p. We can use this equation to perform the division in helping getting the result from 2.          \n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nuse std::collections::HashMap;\n\nimpl Solution {\n    pub fn count_anagrams(s: String) -> i32 {\n        let mut mp = HashMap::<char, i32>::new();\n        let n = s.len();\n        let s = s.chars().collect::<Vec<char>>();\n        let mut ret = 1;\n        \n        for i in 0 ..= n {\n            if i == n || s[i] == \' \' {\n                let data = mp.values().map(|a| *a).collect::<Vec<i32>>();\n                ret = (ret * Self::calculate(&data) as i64) % 1_000_000_007;\n                mp.clear();\n            } else { *mp.entry(s[i]).or_insert(0) += 1; }\n        } \n        \n        ret as _\n    }\n    \n    fn calculate(data: &Vec<i32>) -> i32 {\n        let n = data.iter().sum::<i32>();\n        let mut ret = 1;\n        for k in 2 ..= n {\n            ret = (ret * k as i64) % 1_000_000_007;\n        }\n        \n        for d in data {\n            for k in 2 ..= *d {\n                ret = (ret * Self::divide(k) as i64) % 1_000_000_007;\n            }\n        }\n        \n        ret as _\n    }\n    \n    fn divide(a: i32) -> i32 {\n        let (mut base, mut ret) = (a as i64, 1);\n        let mut m = 1_000_000_005;\n        while m > 0 {\n            if m % 2 == 1 { ret = (ret * base) % 1_000_000_007; }\n            m >>= 1;\n            base = (base * base) % 1_000_000_007;\n        }\n        \n        ret as _\n    }\n}\n```
['Rust']