InclusionExclusion Principle
Credit to https://leetcode.com/problems/number-of-strings-which-can-be-rearranged-to-contain-substring/solutions/4276873/c-o-log-n-0ms-solution-using-pow-inclus
Credit to https://leetcode.com/problems/number-of-strings-which-can-be-rearranged-to-contain-substring/solutions/4276873/c-o-log-n-0ms-solution-using-pow-inclusion-exclusion-principle/ for his amazing explanation ! Understood a lot about Inclusion and Exclusion principle !\n\n**Note:** Think of inclusion and exclusion only when the number of events are less. As if there are more events then calculating the answer would be a big task. As if there were $$n$$ number of events then the number of terms in inclusion and exclusion would be \n$$2$$^$$n - 1$$.\n\n# Code\n```\n// Very similar to Coin Change\n\nclass Solution {\npublic:\n    #define ll long long\n    const int M = 1e9 + 7;\n    ll pow(ll a, ll b){\n        // BASE CASE\n        if(b == 0) return 1;\n        ll tmp = pow(a,b/2);\n        if(b%2 == 0) return (tmp%M*tmp%M)%M;\n        return (a%M*pow(a,b-1)%M)%M;\n    }\n\n    int stringCount(int n) {\n        ll ans = 0ll;\n        // P(A) + P(B) + P(D)\n        ans += pow(25, n) * 3;\n        // P(C)\n        ans += pow(25, n - 1) * n;\n        // P(A\u2229B) + P(A\u2229D) + P(B\u2229D)\n        ans -= pow(24, n) * 3;\n        // P(A\u2229C) + P(C\u2229D)\n        ans -= pow(24, n - 1) * n * 2;\n        // P(A\u2229B\u2229D)\n        ans += pow(23, n);\n        // P(A\u2229C\u2229D)\n        ans += pow(23, n - 1) * n;\n        ans = (pow(26, n) - ans % M + M)%M;\n        return ans;\n    }\n};\n```
['C++']