output_description: Print the sum of the ABC numbers of all the 3^Q strings, modulo 10^9 + 7.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
attempt: import sys
  
  readline = sys.stdin.readline
  MOD = 10**9 + 7
  INF = float("INF")
  sys.setrecursionlimit(10**5)
  
  
  class ModInt:
      MOD = 10**9 + 7
  
      def __init__(self, x):
          self.x = x % MOD
  
      def __str__(self):
          return str(self.x)
  
      def __repr__(self):
          return str(self.x)
  
      def __add__(self, other):
          return (
              ModInt(self.x + other.x)
              if isinstance(other, ModInt)
              else ModInt(self.x + other)
          )
  
      def __sub__(self, other):
          return (
              ModInt(self.x - other.x)
              if isinstance(other, ModInt)
              else ModInt(self.x - other)
          )
  
      def __mul__(self, other):
          return (
              ModInt(self.x * other.x)
              if isinstance(other, ModInt)
              else ModInt(self.x * other)
          )
  
      def __truediv__(self, other):
          return (
              ModInt(self.x * pow(other.x, MOD - 2, MOD))
              if isinstance(other, ModInt)
              else ModInt(self.x * pow(other, MOD - 2, MOD))
          )
  
      def __pow__(self, other):
          return (
              ModInt(pow(self.x, other.x, MOD))
              if isinstance(other, ModInt)
              else ModInt(pow(self.x, other, MOD))
          )
  
      __radd__ = __add__
  
      def __rsub__(self, other):
          return (
              ModInt(other.x - self.x)
              if isinstance(other, ModInt)
              else ModInt(other - self.x)
          )
  
      __rmul__ = __mul__
  
      def __rtruediv__(self, other):
          return (
              ModInt(other.x * pow(self.x, MOD - 2, MOD))
              if isinstance(other, ModInt)
              else ModInt(other * pow(self.x, MOD - 2, MOD))
          )
  
      def __rpow__(self, other):
          return (
              ModInt(pow(other.x, self.x, MOD))
              if isinstance(other, ModInt)
              else ModInt(pow(other, self.x, MOD))
          )
  
      def set_mod_divisor(self, divisor):
          ModInt.MOD = divisor
  
  
  def main():
      s = input()
      n = len(s)
      dp_t = [ModInt(0)] * (n + 1)
      dp_a = [ModInt(0)] * (n + 1)
      dp_ab = [ModInt(0)] * (n + 1)
      dp_abc = [ModInt(0)] * (n + 1)
  
      dp_t[0] = ModInt(1)
      dp_a[0] = ModInt(0)
      dp_ab[0] = ModInt(0)
      dp_abc[0] = ModInt(0)
  
      for i, char in enumerate(s, 1):
          if char == "?":
              dp_t[i] = 3 * dp_t[i - 1]
              dp_a[i] = 3 * dp_a[i - 1] + dp_t[i - 1]
              dp_ab[i] += 3 * dp_ab[i - 1] + dp_a[i - 1]
              dp_abc[i] += 3 * dp_abc[i - 1] + dp_ab[i - 1]
          else:
              dp_t[i] = dp_t[i - 1]
              dp_a[i] += dp_a[i - 1]
              dp_ab[i] += dp_ab[i - 1]
              dp_abc[i] += dp_abc[i - 1]
              if char == "A":
                  dp_a[i] += dp_t[i - 1]
              if char == "B":
                  dp_ab[i] += dp_a[i - 1]
              if char == "C":
                  dp_abc[i] += dp_ab[i - 1]
  
      print(dp_abc[-1])
  
  
  if __name__ == "__main__":
      main()
  
problem_description: Statement
  
  The _ABC number_ of a string T is the number of triples of integers (i, j, k)
  that satisfy all of the following conditions:
  
    * 1 ≤ i < j < k ≤ |T| (|T| is the length of T.)
    * T_i = `A` (T_i is the i-th character of T from the beginning.)
    * T_j = `B`
    * T_k = `C`
  
  For example, when T = `ABCBC`, there are three triples of integers (i, j, k)
  that satisfy the conditions: (1, 2, 3), (1, 2, 5), (1, 4, 5). Thus, the ABC
  number of T is 3.
  
  You are given a string S. Each character of S is `A`, `B`, `C` or `?`.
  
  Let Q be the number of occurrences of `?` in S. We can make 3^Q strings by
  replacing each occurrence of `?` in S with `A`, `B` or `C`. Find the sum of
  the ABC numbers of all these strings.
  
  This sum can be extremely large, so print the sum modulo 10^9 + 7.
samples: [{"input": "A??C", "output": "8\n    \n\nIn this case, Q = 2, and we can make 3^Q = 9 strings by by replacing each\noccurrence of `?` with `A`, `B` or `C`. The ABC number of each of these\nstrings is as follows:\n\n  * `AAAC`: 0\n  * `AABC`: 2\n  * `AACC`: 0\n  * `ABAC`: 1\n  * `ABBC`: 2\n  * `ABCC`: 2\n  * `ACAC`: 0\n  * `ACBC`: 1\n  * `ACCC`: 0\n\nThe sum of these is 0 + 2 + 0 + 1 + 2 + 2 + 0 + 1 + 0 = 8, so we print 8\nmodulo 10^9 + 7, that is, 8.\n\n* * *"}, {"input": "ABCBC", "output": "3\n    \n\nWhen Q = 0, we print the ABC number of S itself, modulo 10^9 + 7. This string\nis the same as the one given as an example in the problem statement, and its\nABC number is 3.\n\n* * *"}, {"input": "????C?????B??????A???????", "output": "979596887\n    \n\nIn this case, the sum of the ABC numbers of all the 3^Q strings is\n2291979612924, and we should print this number modulo 10^9 + 7, that is,\n979596887."}]