Python/Math inclusion/exclusion principle. With a very detailed proof. Runs in log time
Intuition\n\nThis is a math problem and an interesting one. It can teach you very important combinatorial concept: inclusion/exclusion principle.\n\nAs in many 
# Intuition\n\nThis is a math problem and an interesting one. It can teach you very important combinatorial concept: [inclusion/exclusion principle](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle).\n\nAs in many things in counting instead of counting directly how many good string do you have, you can count how many bad do you have. And then subtract it from all strings $26^n$.\n\nNow what constitutes a bad string. It should have conditions:\n\n - zero `L` characters: $C_1$\n - zero `T` characters: $C_2$\n - zero `E` characters: $C_3$\n - one  `E` character : $C_4$\n\nNot that it can be any combinations of it which hints that you should use I/E principle. You can see the general formula and for non-math people it might look complicated, but you can write it down for elements as (here I will ommit $|x|$ which means the cardinality of a set of $x$):\n\n$C_1 + C_2 + C_3 + C_4 \\\\\n- (C_1 \\bigcap  C_2 + C_1 \\bigcap  C_3 + C_1 \\bigcap  C_4 + C_2 \\bigcap  C_3 + C_2 \\bigcap  C_4 + C_3 \\bigcap  C_4)  \\\\\n+ C_1 \\bigcap  C_2 \\bigcap C_3 + C_1 \\bigcap  C_2 \\bigcap C_4 + C_1 \\bigcap  C_3 \\bigcap C_4 + C_2 \\bigcap  C_3 \\bigcap C_4 \\\\\n- C_1 \\bigcap C_2 \\bigcap C_3 \\bigcap C_4\n$\n\nThis is a lot of math. What it means is to calculate how many strings of length $n$ will you have with some overlapping conditions. So lets calcualte **the first line:**\n\n - $C_1$ every character can be used but not `L`. $25^n$. $C_2$ and $C_3$ are absolutely the same.\n - $C_4$. One character is `E` and you can put it at any position $n$ and $n - 1$ any 25 characters. So $n \\cdot 25^{n - 1}$\n\n**Now second line:**\n\n - $C_1 \\bigcap  C_2$ you do not have both L and T characters. So $24^n$. $C_1 \\bigcap  C_3$ and $C_2 \\bigcap  C_3$ are the same.\n - $C_1 \\bigcap  C_4$. Similar to last point in first line: $n \\cdot 24^{n - 1}$. Same as $C_2 \\bigcap C_4$\n - $C_3 \\bigcap C_4$. It is not possible to both have zero letters E and one letter E, so it is 0. Remember this case as many in the next line will be the same.\n \n**Third line:**\n\n - $C_1 \\bigcap  C_2 \\bigcap C_3$ is $23^n$\n - $C_1 \\bigcap  C_2 \\bigcap C_4$ is $n \\cdot 23^{n - 1}$. \n - $C_1 \\bigcap  C_3 \\bigcap C_4$ is 0. See last point in second line. Same as $C_2 \\bigcap  C_3 \\bigcap C_4$\n \n**Forth line**\n\n - It also have a $C_3 \\bigcap C_4$ so the answer is 0\n\nNow all you need is to add and subtract them. After very rudimentary math you will get $25^{n - 1} \\cdot (75 + n) - 24^{n - 1} \\cdot (72 + 2n) + 23^{n - 1} \\cdot (23 + n$. Now all you need to subtract it from our $26^n$.\n\n$a^n$ can be found in log time via squaring, and n Python you already have it.\n\n\n\n# Complexity\n- Time complexity: $O(\\log n)$\n- Space complexity: $O(1)$\n\n# Code\n```\nclass Solution:\n  def stringCount(self, n: int) -> int:\n    MOD = 10**9 + 7\n    tmp = pow(25, n - 1, MOD) * (75 + n) - pow(24, n - 1, MOD) * (72 + 2 * n) + pow(23, n - 1) * (23 + n)\n    return (pow(26, n, MOD) - tmp) % MOD\n```
['Math', 'Python']