{"problem":{"name":"We Love ABC","description":{"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: *   $1 ≤ i < j < k ≤ |T|$ ($|T|$ is the length of $T$.) *   $T_i =$ `A`","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc104_d"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $3 ≤ |S| ≤ 10^5$\n*   Each character of $S$ is `A`, `B`, `C` or `?`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc104_d","tags":[],"sample_group":[["A??C","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$."],["ABCBC","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$."],["????C?????B??????A???????","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$."]],"created_at":"2026-03-03 11:01:14"}}