分数: 400 点
问题陈述
的 ABC 号码 字符串的 一个字符串的 T 是整数三元组的数量 (i, j, k) 满足以下所有条件:
- 1 ≤ i < j < k ≤ |T| (|T| 是长度 T.)
- T_i =
A(T_i 是 i- 第一个字符 T 从头开始。) - T_j =
B - T_k =
C
例如,当 T = ABCBC,有三个整数三元组 (i, j, k) 满足条件: (1, 2, 3), (1, 2, 5), (1, 4, 5)。因此,ABC 数为 T is 3.
给你一个字符串 S。的每个字符 S is A, B, C or ?.
让 Q 是出现的次数 ? in S。我们可以使 3^Q 字符串,替换每次出现的 ? in S 与 A, B or C。求所有这些字符串的 ABC 数之和。
这个总和可能非常大,所以打印总和模 10^9 + 7.
约束
- 3 ≤ |S| ≤ 10^5
- 每个字符 S is
A,B,Cor?.
输入
输入由标准输入按以下格式给出:
S
输出
打印所有ABC数字的总和 3^Q 字符串,模数 10^9 + 7.
示例输入 1
A??C
示例输出 1
8
在这种情况下, Q = 2,我们可以使 3^Q = 9 字符串通过替换每个出现的 ? 与 A, B or C。每个字符串的 ABC 数如下:
AAAC: 0AABC: 2AACC: 0ABAC: 1ABBC: 2ABCC: 2ACAC: 0ACBC: 1ACCC: 0
这些的总和是 0 + 2 + 0 + 1 + 2 + 2 + 0 + 1 + 0 = 8,所以我们打印 8 模数 10^9 + 7,即 8.
示例输入 2
ABCBC
示例输出 2
3
当 Q = 0,我们打印 ABC 数 S 本身,模 10^9 + 7。该字符串与问题陈述中给出的示例相同,其 ABC 编号为 3.
示例输入 3
????C?????B??????A???????
示例输出 3
979596887
在这种情况下,所有的 ABC 数之和 3^Q 字符串是 2291979612924,我们应该打印这个数字模数 10^9 + 7,即 979596887.