{"raw_statement":[{"iden":"problem statement","content":"The _ABC number_ of a string $T$ is the number of triples of integers $(i, j, k)$ that satisfy all of the following conditions:\n\n*   $1 ≤ i < j < k ≤ |T|$ ($|T|$ is the length of $T$.)\n*   $T_i =$ `A` ($T_i$ is the $i$\\-th character of $T$ from the beginning.)\n*   $T_j =$ `B`\n*   $T_k =$ `C`\n\nFor 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$.\nYou are given a string $S$. Each character of $S$ is `A`, `B`, `C` or `?`.\nLet $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.\nThis sum can be extremely large, so print the sum modulo $10^9 + 7$."},{"iden":"constraints","content":"*   $3 ≤ |S| ≤ 10^5$\n*   Each character of $S$ is `A`, `B`, `C` or `?`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$S$"},{"iden":"sample input 1","content":"A??C"},{"iden":"sample output 1","content":"8\n\nIn this case, $Q = 2$, and we can make $3^Q = 9$ strings by by replacing each occurrence of `?` with `A`, `B` or `C`. The ABC number of each of these strings 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$ modulo $10^9 + 7$, that is, $8$."},{"iden":"sample input 2","content":"ABCBC"},{"iden":"sample output 2","content":"3\n\nWhen $Q = 0$, we print the ABC number of $S$ itself, modulo $10^9 + 7$. This string is the same as the one given as an example in the problem statement, and its ABC number is $3$."},{"iden":"sample input 3","content":"????C?????B??????A???????"},{"iden":"sample output 3","content":"979596887\n\nIn this case, the sum of the ABC numbers of all the $3^Q$ strings is $2291979612924$, and we should print this number modulo $10^9 + 7$, that is, $979596887$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}