数子序列ABC
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Background
Special for beginners, ^_^
Description
一个字符串能够找到多少个这样的子序列依次出现 A 、 B 、 C 这三个字母。
如果某个位置是 ? ，那么该位置可以替换为 A 、 B 、 C 中的任何一个。如果有两个位置是 ? ，可以得到九个只含有 ABC 的字母串。
问所有 ABC 字母串的 ABC 子序列有多少个？
Format
Input
一个只包含 A 、 B 、 C 和 ? 的字符串。
长度在 3 到 之间。
Output
在一行中输出对 取模后的答案。
Samples
ABC?
4
Limitation
1s, 1024KiB for each test case.
