该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

康康喜欢玩字符串，有一天遇到一些字符串，已知这些字符串中只包含’C’, ‘A’, ‘T’三种字母。他想知道该字符串中共有多少个可以构成CAT的子序列。
输入只有一行，是一个只包含’C’, ‘A’, ‘T’三种字母的字符串，长度不超过1e6 。
输出一行，为CAT的数量，由于数量可能比较大，请把结果对1000000007取模。

样例

输入

CCACTAT

输出

7

解释：
下标组合分别是：024，026，124，126，056，156，356共7个CAT