content: public class Solution {
      int M = 1000000007;
      public int numDecodings(String s) {
          Long[] memo = new Long[s.length()];
          return (int) ways(s, s.length() - 1, memo);
      }
      public long ways(String s, int i, Long[] memo) {
          if (i < 0)
              return 1;
          if (memo[i] != null)
              return memo[i];
          if (s.charAt(i) == '*') {
              long res = 9 * ways(s, i - 1, memo) % M;
              if (i > 0 && s.charAt(i - 1) == '1')
                  res = (res + 9 * ways(s, i - 2, memo)) % M;
              else if (i > 0 && s.charAt(i - 1) == '2')
                  res = (res + 6 * ways(s, i - 2, memo)) % M;
              else if (i > 0 && s.charAt(i - 1) == '*')
                  res = (res + 15 * ways(s, i - 2, memo)) % M;
              memo[i] = res;
              return memo[i];
          }
          long res = s.charAt(i) != '0' ? ways(s, i - 1, memo) : 0;
          if (i > 0 && s.charAt(i - 1) == '1')
              res = (res + ways(s, i - 2, memo)) % M;
          else if (i > 0 && s.charAt(i - 1) == '2' && s.charAt(i) <= '6')
              res = (res + ways(s, i - 2, memo)) % M;
          else if (i > 0 && s.charAt(i - 1) == '*')
              res = (res + (s.charAt(i) <= '6' ? 2 : 1) * ways(s, i - 2, memo)) % M;
          memo[i] = res;
          return memo[i];
      }
  }