[C++]Beats 100% Detailed Explanation Modulo Inverse and Fermat Theorem
Approach/Explanation  \n Describe your first thoughts on how to solve this problem. \nYou need knowledge of modulo inverse and fermat theorem to solve this prob
# Approach/Explanation  \n<!-- Describe your first thoughts on how to solve this problem. -->\nYou need knowledge of **modulo inverse** and **fermat theorem** to solve this problem\n\nMODULO INVERSE SAYS\n1. (a+b)%m = (a%m + b%m)%m \n2. (a-b)%m = (a%m - b%m + **m**)%m    \n> in case "a%m - b%m" is negative the highlighted \'\'m\'\' is added\n3. (a*b)%m = (a%m * b%m)%m\n\nwe can\'t apply the same formula for divison though\nso we use FERMAT THEOREM for that\nit says\n(a/b)= (a*b^-1)\n(a*b^-1)%m = (a%m * b*-1%m)%m\nthis further can be reduced to\n(a/b)%m = (a%m * b^(m-2)%m)%m    (not proving this)\n\n\n***This is all you need to know for solving this problem\nGive it a try first\nthen see my code***\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nDepends on how long the string is.\nAvg case time complexity = O(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(1) (excluding the hash array of size 128)\n\n![Screenshot 2024-06-05 191641.png](https://assets.leetcode.com/users/images/14b235b2-fa78-41f6-8884-2a5d3beeab75_1717595797.0444746.png)\n\n\n\n# Code\n```\nclass Solution {\npublic:\n    int modinverse(int b){\n        int k = 1e9+5, mod = 1e9+7,ans = 1;\n        while(k){\n            if(k&1){ //if k is odd\n                ans = (ans*1LL*b)%mod;\n            }\n            b = (b*1LL*b)%mod;\n            k >>= 1; //equivalent to k / 2\n        }\n        return ans;\n    }\n    int countAnagrams(string s) {\n\n        unsigned long long int ans = 1;\n        unsigned long long int f1 = 1;\n        unsigned long long int d = 1, f = 1, p = 0;\n        vector<int> h(128, 0);\n        int i = 0;\n        for (int i = 0; i <= s.size(); i++) {\n            if (s[i] == \' \' || i == s.size()) {\n                f1 = f/d;\n                if (f1 >= (1000000007)) {\n                    f1 = f1 % 1000000007;\n                }               \n                ans *= f1;\n                if (ans >= (1000000007)) {\n                    ans = ans % 1000000007;\n                }           \n                fill(h.begin(), h.end(), 0);\n                d = 1;\n                f = 1;\n                p = 0;\n            } else {\n                p++;\n                f *= p;              \n                if (h[s[i]] != 0) {\n                    h[s[i]]++;\n                    d *= h[s[i]];\n                } else\n                    h[s[i]]++;\n                if(f==d){f=1;d=1;}                        \n                if(f > 1e9+7)\n                {\n                    f=((f%1000000007)*modinverse(d))%1000000007;\n                    d=1;\n                }                      \n            }\n        }\n        return ans;\n    }\n};\n```
['C++']