Alice is texting Bob using her phone. The mapping of digits to letters is shown in the figure below.

In order to add a letter, Alice has to press the key of the corresponding digit i times, where i is the position of the letter in the key.


	For example, to add the letter 's', Alice has to press '7' four times. Similarly, to add the letter 'k', Alice has to press '5' twice.
	Note that the digits '0' and '1' do not map to any letters, so Alice does not use them.


However, due to an error in transmission, Bob did not receive Alice's text message but received a string of pressed keys instead.


	For example, when Alice sent the message "bob", Bob received the string "2266622".


Given a string pressedKeys representing the string received by Bob, return the total number of possible text messages Alice could have sent.

Since the answer may be very large, return it modulo 109 + 7.

&nbsp;
Example 1:

Input: pressedKeys = "22233"
Output: 8
Explanation:
The possible text messages Alice could have sent are:
"aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae", and "ce".
Since there are 8 possible messages, we return 8.


Example 2:

Input: pressedKeys = "222222222222222222222222222222222222"
Output: 82876089
Explanation:
There are 2082876103 possible text messages Alice could have sent.
Since we need to return the answer modulo 109 + 7, we return 2082876103 % (109 + 7) = 82876089.


&nbsp;
Constraints:


	1 &lt;= pressedKeys.length &lt;= 105
	pressedKeys only consists of digits from '2' - '9'.


class Solution(object):
    def countTexts(self, pressedKeys):
        """
        :type pressedKeys: str
        :rtype: int
        """
        dp = [1] + [0]*len(pressedKeys)
        mod = 10**9 + 7
        for i, n in enumerate(pressedKeys):
            dp[i+1] = dp[i]
            # check if is continous
            if i >= 1 and pressedKeys[i-1] == n:
                dp[i+1] += dp[i-1]
                dp[i+1] %= mod
                if i >= 2 and pressedKeys[i-2] == n:
                    dp[i+1] += dp[i-2]
                    dp[i+1] %= mod
                    # Special case for '7' and '9' that can have 4 characters combination
                    if i >= 3 and pressedKeys[i-3] == n and (n == "7" or n == "9"):
                        dp[i+1] += dp[i-3]
                        dp[i+1] %= mod
        return dp[-1]
class Solution {
    int mod = (1000000007);

    public int countTexts(String pressedKeys) {
        int[] key = new int[] { 0, 0, 3, 3, 3, 3, 3, 4, 3, 4 };
        int n = pressedKeys.length();
        return solve(0,pressedKeys,key);
    }

    public int solve(int ind, String s, int[] key) {
        if (ind == s.length()) {
            return 1;
        }
        int count = 0;
        int num = s.charAt(ind) - '0';
        int rep = key[num];
        for (int i = 0; i < rep && ind + i < s.length() && s.charAt(ind) == s.charAt(ind + i); i++) {
            count += solve(ind + 1 + i, s, key);
            count %= mod;
        }
        return  count;
    }
}
class Solution {
public:
    int mod = 1e9+7;
    int solve(string &str, int idx) {
        if(idx == str.length()) return 1;
        int maxKeyPress = (str[idx] == '7' || str[idx] == '9') ? 4 : 3;
        long long currIndex = idx, pressFrequency = 1, ans = 0;
        while(pressFrequency <= maxKeyPress && str[currIndex] == str[idx]) {
            ++currIndex;
            ++pressFrequency;
            ans += solve(str, currIndex) % mod;
        }
        return ans%mod;
    }
    int countTexts(string pressedKeys) {
        return solve(pressedKeys, 0) % mod;
    }
};
var countTexts = function(pressedKeys) {
    const MOD = 1e9 + 7;
    const n = pressedKeys.length;
    const dp = new Array(n + 1).fill(0);

    dp[0] = 1;

    let lastChar = "";
    let repeatCount = 0;

    for (let i = 1; i <= n; ++i) {
        const currChar = pressedKeys[i - 1];

        if (currChar != lastChar) repeatCount = 0;

        lastChar = currChar;
        repeatCount += 1;

        dp[i] = (dp[i] + dp[i - 1]) % MOD;

        if (i >= 2 && repeatCount >= 2) dp[i] = (dp[i] + dp[i - 2]) % MOD;
        if (i >= 3 && repeatCount >= 3) dp[i] = (dp[i] + dp[i - 3]) % MOD;
        if ((currChar == "7" || currChar == "9") && i >= 4 && repeatCount >= 4) dp[i] = (dp[i] + dp[i - 4]) % MOD;
     }

    return dp[n];
};
Count Number of Texts