<p>A message containing letters from <code>A-Z</code> can be <strong>encoded</strong> into numbers using the following mapping:</p>

<pre>
&#39;A&#39; -&gt; &quot;1&quot;
&#39;B&#39; -&gt; &quot;2&quot;
...
&#39;Z&#39; -&gt; &quot;26&quot;
</pre>

<p>To <strong>decode</strong> an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, <code>&quot;11106&quot;</code> can be mapped into:</p>

<ul>
	<li><code>&quot;AAJF&quot;</code> with the grouping <code>(1 1 10 6)</code></li>
	<li><code>&quot;KJF&quot;</code> with the grouping <code>(11 10 6)</code></li>
</ul>

<p>Note that the grouping <code>(1 11 06)</code> is invalid because <code>&quot;06&quot;</code> cannot be mapped into <code>&#39;F&#39;</code> since <code>&quot;6&quot;</code> is different from <code>&quot;06&quot;</code>.</p>

<p><strong>In addition</strong> to the mapping above, an encoded message may contain the <code>&#39;*&#39;</code> character, which can represent any digit from <code>&#39;1&#39;</code> to <code>&#39;9&#39;</code> (<code>&#39;0&#39;</code> is excluded). For example, the encoded message <code>&quot;1*&quot;</code> may represent any of the encoded messages <code>&quot;11&quot;</code>, <code>&quot;12&quot;</code>, <code>&quot;13&quot;</code>, <code>&quot;14&quot;</code>, <code>&quot;15&quot;</code>, <code>&quot;16&quot;</code>, <code>&quot;17&quot;</code>, <code>&quot;18&quot;</code>, or <code>&quot;19&quot;</code>. Decoding <code>&quot;1*&quot;</code> is equivalent to decoding <strong>any</strong> of the encoded messages it can represent.</p>

<p>Given a string <code>s</code> consisting of digits and <code>&#39;*&#39;</code> characters, return <em>the <strong>number</strong> of ways to <strong>decode</strong> it</em>.</p>

<p>Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;*&quot;
<strong>Output:</strong> 9
<strong>Explanation:</strong> The encoded message can represent any of the encoded messages &quot;1&quot;, &quot;2&quot;, &quot;3&quot;, &quot;4&quot;, &quot;5&quot;, &quot;6&quot;, &quot;7&quot;, &quot;8&quot;, or &quot;9&quot;.
Each of these can be decoded to the strings &quot;A&quot;, &quot;B&quot;, &quot;C&quot;, &quot;D&quot;, &quot;E&quot;, &quot;F&quot;, &quot;G&quot;, &quot;H&quot;, and &quot;I&quot; respectively.
Hence, there are a total of 9 ways to decode &quot;*&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;1*&quot;
<strong>Output:</strong> 18
<strong>Explanation:</strong> The encoded message can represent any of the encoded messages &quot;11&quot;, &quot;12&quot;, &quot;13&quot;, &quot;14&quot;, &quot;15&quot;, &quot;16&quot;, &quot;17&quot;, &quot;18&quot;, or &quot;19&quot;.
Each of these encoded messages have 2 ways to be decoded (e.g. &quot;11&quot; can be decoded to &quot;AA&quot; or &quot;K&quot;).
Hence, there are a total of 9 * 2 = 18 ways to decode &quot;1*&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;2*&quot;
<strong>Output:</strong> 15
<strong>Explanation:</strong> The encoded message can represent any of the encoded messages &quot;21&quot;, &quot;22&quot;, &quot;23&quot;, &quot;24&quot;, &quot;25&quot;, &quot;26&quot;, &quot;27&quot;, &quot;28&quot;, or &quot;29&quot;.
&quot;21&quot;, &quot;22&quot;, &quot;23&quot;, &quot;24&quot;, &quot;25&quot;, and &quot;26&quot; have 2 ways of being decoded, but &quot;27&quot;, &quot;28&quot;, and &quot;29&quot; only have 1 way.
Hence, there are a total of (6 * 2) + (3 * 1) = 12 + 3 = 15 ways to decode &quot;2*&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s[i]</code> is a digit or <code>&#39;*&#39;</code>.</li>
</ul>

class Solution {
public:
  long long int solve(string &s,int index,int n, long long int m,vector<long long >&dp)
  {
    if (index>=n)
    return 1;
    if (s[index]=='0')
    return INT_MIN;

    if(dp[index]!=-1){
        return dp[index];
    }

    // single 
    long long int a=0;
    if (s[index]=='*')
    {
        for(int i=1;i<10;i++)
        {
          long long b =solve (s,index+1,n,m,dp);
          if (b>0)
          a+=b;
          a=a%m;
        }
    }
    else 
    {
          long long b =solve (s,index+1,n,m,dp);
          if (b>0)
          a+=b;
          a=a%m;
    }
    //double 
    if (index<n-1)
    {
        if(s[index]!='*' && s[index+1]!='*')
        {
            int num=(s[index]-'0');
            num = num*10 + (s[index+1]-'0');
            if(num>=10 && num<=26){
                long long b =solve (s,index+2,n,m,dp);
                if (b>0)
                a+=b;
                a=a%m;
            }
        }
        else if(s[index]=='*' && s[index+1]!='*')
        {
            for(int i=1;i<=2;i++)
            {
                int num = i;
                num = num*10 + (s[index+1]-'0');
                if(num>=10 && num<=26){
                    long long b =solve (s,index+2,n,m,dp);
                    if (b>0)
                    a+=b;
                    a=a%m;
                }
            } 
        }
        else if(s[index]!='*' && s[index+1]=='*')
        {   
            if((s[index]-'0')<3){
                for(int i=1;i<10;i++)
                {
                    int num = (s[index]-'0');
                    num = num*10 + i;
                    if(num>=10 && num<=26){
                        long long b =solve (s,index+2,n,m,dp);
                        if (b>0)
                        a+=b;
                        a=a%m;
                    }
                }
            }
        }
        else
        {
            for(int j=1;j<3;j++){
                for(int i=1;i<10;i++)
                {
                    int num = j;
                    num = num*10 + i;
                    if(num>=10 && num<=26){
                        long long b =solve (s,index+2,n,m,dp);
                        if (b>0)
                        a+=b;
                        a=a%m;
                    }
                }
            }
        }
    }
    return dp[index] = a%m;
  }
    int numDecodings(string s) {
    long long int m =1e9+7;
    vector<long long int>dp(s.size()+1,-1);
    long long int ans=solve(s,0,s.size(),m,dp);
    if(ans<0)return 0;
    return ans%m;
    }
};
37003