3-bonacci and 4-bonacci Bottom up DP O(N) + modular exponentiation.
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

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

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

# Code
```java []
class Solution {
    private static final int MOD = (int)1e9 + 7;
    public int countTexts(String pressedKeys) {
        /*
        handle 9's and 7's seperately to others as they have 4 letters, focus on 3 letter first.

        Observe case where we repeat the same three letter key x i times. let a = 1 press letter, b = 2 press, c = 3 press
            i = 1: 1 combo {a}
            i = 2: 2 combos {aa, b}
            i = 3: 4 combos {aaa, ab, ba, c}
            i = 4: {aaaa, aab, aba, baa, bb, ca, ac} 7 combos.
            If looking at strictly letter counts (ignoring permutations for now), this is the same way as breaking up i into sums of 1's 2's and 3's. 

            to parse x can also look at different ways of "cutting off the prefix" i.e. if have xxxxxxx... can parse as x | xxxx... xx | xxx... xxx | xx...
            this gives a | (i-1) x's, b | (i-2) x's, c (i-3) x's. Since the first letter must obviously be an a, b, or c, this accounts for all cases.
            if let the number of diff texts to make with i of the same three letter key presses = dp[i] this gives
            dp[i] = dp[i-1] (first a) + dp[i-2] (first b) + dp[i-3] (first c). 
            This is just a tribonacci number....

        For the case with four letters, this logic should generalize to give a 4-bonacci number. 

        Thus can calculate 3 and 4 bonacci numbers and just take product as they appear. 
        */
        int n = pressedKeys.length(), max3Streak = 0, max4Streak = 0, streak = 1;

        if(n == 1) return 1;
        if(n == 2) return pressedKeys.charAt(0) == pressedKeys.charAt(1) ? 2 : 1;
        
        int[] streak3Cnts = new int[n+1], streak4Cnts = new int[n+1];
        for(int i = 1; i <= n; i++) {
            if(i < n && pressedKeys.charAt(i) == pressedKeys.charAt(i-1)) {
                streak++;
            } else {
                if(pressedKeys.charAt(i-1) == '9' || pressedKeys.charAt(i-1) == '7') {
                    streak4Cnts[streak]++;
                    max4Streak = Math.max(streak, max4Streak);
                } else {
                    streak3Cnts[streak]++;
                    max3Streak = Math.max(streak, max3Streak);
                }
                streak = 1;
            }
        }


        long res = 1;
        res = (res * modExp(2, streak3Cnts[2] + streak4Cnts[2])) % MOD; 
        res = (res * modExp(4, streak3Cnts[3] + streak4Cnts[3])) % MOD;

        long t1 = 1, t2 = 2, t3 = 4;
        for(streak = 4; streak <= max3Streak; streak++) {
            long trib = (t1 + t2 + t3) % MOD;
            res = (res * modExp(trib, streak3Cnts[streak])) % MOD;
            t1 = t2;
            t2 = t3;
            t3 = trib;
        }
        
        long f1 = 1, f2 = 2, f3 = 4, f4 = 8;
        for(streak = 4; streak <= max4Streak; streak++) {
            res = (res * modExp(f4, streak4Cnts[streak])) % MOD;
            long next = (f1 + f2 + f3 + f4) % MOD;
            f1 = f2;
            f2 = f3;
            f3 = f4;
            f4 = next;
        }

        return (int)res;

    }


    private long modExp(long base, int exp) {
        if(exp < 8) return linearModExp(base, exp);
        long mult = base, res = 1;
        while(exp > 0) {
            if((exp & 1) == 1) res = (res * mult) % MOD;
            mult = (mult * mult) % MOD;
            exp >>= 1;
        }
        return res;
    }

    private long linearModExp(long base, int exp) {
        long res = 1;
        while(exp-- > 0) res = (res * base) % MOD;
        return res;
    }
}
```
['Math', 'Dynamic Programming', 'Java']