The string APPAPT contains two PAT's as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.

Now given any string, you are supposed to tell the number of PAT's contained in the string.

Input Specification:

Each input file contains one test case. For each case, there is only one line giving a string of no more than 105 characters containing only P, A, or T.

Output Specification:

For each test case, print in one line the number of PAT's contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.

Sample Input:

APPAPT

Sample Output:

2

题意：

        计算有几种组成PAT的方案

思路：

        记录T的总数（作为某位置右边T的个数）

        实时计算P的数量，遇到T总数减一，遇到A则此时P数xT数为这个A能够组成的PAT数量

注意：

        大数运算时需避免溢出，进行取余（对1000000007）

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String str = st.nextToken();
        int n = str.length();

        int Psum = 0;
        int Tsum = 0;
        final int MOD = 1000000007;  // 常量定义，方便维护

        // 先统计所有T的总数（右侧T的初始数量）
        for (int i = 0; i < n; i++) {
            if (str.charAt(i) == 'T') {
                Tsum++;
            }
        }

        int res = 0;
        // 修复1：循环范围改为i < n，遍历所有字符
        for (int i = 0; i < n; i++) {
            char c = str.charAt(i);
            if (c == 'P') {
                Psum++;  // 遇到P，左侧P数量+1
            } else if (c == 'T') {
                Tsum--;  // 遇到T，右侧T数量-1（当前T之后的T减少）
            } else if (c == 'A') {
                // 计算当前A的有效组合数，并取模
                int ans = (int)(((long)(Psum % MOD) * (Tsum % MOD)) % MOD);
                res = (res + ans) % MOD;  // 修复2：累加后对结果取模，防止溢出
            }
        }

        System.out.println(res);
    }
}