← 返回题目列表

AtCoder · abc104_d

D. 我们爱ABC

中文机器翻译题面 查看原题

分数: 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, C or ?.

输入

输入由标准输入按以下格式给出:

S

输出

打印所有ABC数字的总和 3^Q 字符串,模数 10^9 + 7.


示例输入 1

A??C

示例输出 1

8

在这种情况下, Q = 2,我们可以使 3^Q = 9 字符串通过替换每个出现的 ? 与 A, B or C。每个字符串的 ABC 数如下:

  • AAAC: 0
  • AABC: 2
  • AACC: 0
  • ABAC: 1
  • ABBC: 2
  • ABCC: 2
  • ACAC: 0
  • ACBC: 1
  • ACCC: 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.