Math, Union rule and proof
IntuitionIt's definitely a Math problem, I was having trouble counting valid string, then immediately I came up with counting invalid string solution!!ApproachT
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
It's definitely a Math problem, I was having trouble counting valid string, then immediately I came up with counting invalid string solution!!
# Approach
<!-- Describe your approach to solving the problem. -->
To form the formula, I did some Maths, here is my formula and proof : 
`S = 0L + 0E + 0T + 1E - 0L0E - 0L0T - 0E0T - 0T1E -0L1E +0L0T1E + 0L0T0E`
where : 
`0L : Has 0 char L `
`0E : Has 0 char E`
`0T : Has 0 char T`
` 1E : Has 1 char E`
Proof 1 : Using diagram
\- level 1
![image.png](https://assets.leetcode.com/users/images/353c773a-da4c-4dd4-be98-a56bcbd52016_1740548768.8371487.png)
\- level 2
![2.png](https://assets.leetcode.com/users/images/ddae1e56-ba95-419b-9689-e92d1574d7e6_1740548784.0666912.png)

\- level 3
![3.png](https://assets.leetcode.com/users/images/771e2c52-06ff-47ca-bc7c-0a66c90fa2d5_1740548789.6749701.png)

Proof 2 : Using union rule

![image.png](https://assets.leetcode.com/users/images/f9ac2676-057b-418f-9a4f-541ac79d4fd2_1740548888.0325446.png)


# Complexity
- Time complexity: O(logn)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(1)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
const long mod=1000000007;
class Solution {
    long pow(long x, int n){
        if(x>mod) x%=mod;
        if(n==0) return 1;
        if(n%2) return x*pow(x*x,n/2)%mod;
        return pow(x*x,n/2)%mod;
    }
public:
    int stringCount(int n) {
        if(n<4) return 0;
        // 0L + 0E + 0T + 1E
        // - 0L0E - 0L0T - 0E0T - 0T1E -0L1E
        //+0L0T1E + 0L0T0E

        //25^(n)+25^(n)+25^(n)+n*25^(n-1)
        //-24^(n)-24^(n)-24^(n) - n*24^(n-1) - n*24^(n-1)
        //+23^(n)+n*23^(n-1)
        
        // long res=3*pow(25,n) + n*pow(25,n-1)%mod \
        // - 3*pow(24,n) - 2*n*pow(24,n-1)%mod \
        // + pow(23,n) + n*pow(23,n-1)%mod;
        
        long res=(3*25+n)*pow(25,n-1)%mod \
        - (3*24+2*n)*pow(24,n-1)%mod \
        + (23+n)*pow(23,n-1)%mod;

        res=(pow(26,n)-res+mod*mod)%mod;
        return res; 
    }
};
```
['C++']