✅☑️ Java Solution || Count-anagrams || Using Fermat's Little Theorem
mul(long a, long b): Performs multiplication (a * b) % mod in a way that handles large numbers by taking the modulo at each step.\n\nbinaryExpo(long a, long n):
**mul(long a, long b):** Performs multiplication (a * b) % mod in a way that handles large numbers by taking the modulo at each step.\n\n**binaryExpo(long a, long n):** Implements binary exponentiation to efficiently calculate a^n % mod. This method reduces the computational complexity by halving n at each recursive step.\n\n**countAnagrams(String s):** Main method to calculate the product of the number of anagrams that can be formed from each word in the input string s.\n\n**Fermat\'s little theorm for Modulo inverse:**\nhttps://en.wikipedia.org/wiki/Fermat%27s_little_theorem#:~:text=Pierre%20de%20Fermat%20first%20stated,1%20is%20divisible%20by%20p. \n\nTime Complexity : \nIf we consider L as the total length of the input string and W as the number of words, the overall time complexity can be approximated as\nO(n)+O(L)+W.O(logn), simplifying to \n\n**O(n+L+Wlogn)**\n\nPlease upvote if you like\n\n# Code\n```\nclass Solution {\n    int mod = (int) (Math.pow(10, 9) + 7);\n\n    public int [] calculateFactorial(int n) {\n        int [] fact = new int[n+1];\n        fact[0] = fact[1] = 1;\n        for(int i=2; i<=n; i++)\n            fact[i] = (int)mul(i , fact[i-1] );\n        return fact;\n    }\n\n    public long mul(long a, long b) {\n        return ((a%mod) * (b%mod))%mod;\n    }\n    public long binaryExpo(long a, long n) {\n        if(n == 0)\n            return 1;\n        long partialAns = binaryExpo(a, n/2);\n        partialAns = mul(partialAns, partialAns);\n        if(n%2==0)\n            return partialAns;\n        return mul(partialAns, a);\n    }\n    public int countAnagrams(String s) {\n        int n = s.length();\n        int[] fact = calculateFactorial(n);\n        long result = 1;\n        String [] strArr = s.split(" ");\n        for(String str : strArr) {\n            int [] freq = new int[26];\n            for(char ch : str.toCharArray())\n                freq[ch - \'a\']++;\n            \n            //anagrams of current word will\n            //n! / !freq[char...to ...length]\n            long curr = 1;\n            for(int fr : freq)\n                curr = mul(curr , fact[fr]);\n\n            curr = mul(fact[str.length()] , binaryExpo(curr, mod - 2));\n\n            result = mul(result, curr);\n        }\n        return (int)result;\n    }\n}\n```\n
['Number Theory', 'Java']