字符串APPAPT中包含了两个单词“PAT”，其中第一个PAT是第2位(P),第4位(A),第6位(T)；第二个PAT是第3位(P),第4位(A),第6位(T)。

现给定字符串，问一共可以形成多少个PAT？

输入格式：

输入只有一行，包含一个字符串，长度不超过105，只包含P、A、T三种字母。

输出格式：

在一行中输出给定字符串中包含多少个PAT。由于结果可能比较大，只输出对1000000007取余数的结果。

输入样例：

APPAPT

输出样例：

2

解法1
以字符A分隔字符串，countP[i]表示第i-1个A到第i个A之间P的个数，countT[i]表示第i个到第i+1个A之间T的个数，t表示T的总数。

#include<stdio.h>
int countP[100000]={0};
int countT[100000]={0};
int main()
{
    char c;
    int i=0;
    int t=0;
    while((c=getchar())!='\n')
    {
        if(c=='P')
            countP[i]++;
        else if(c=='A')
            i++;
        else if(c=='T')
        {
            countT[i]++;t++;
        }
    }
    int j=0,count=0;
    int p=countP[0];
    t-=countT[0];
    for(j=1;j<=i;j++)
    {
        count = (count+p*t)%1000000007;
        p+=countP[j];
        t-=countT[j];
    }
    printf("%d",count);
    return 0;
}

解法2

#include<stdio.h>
int main()
{
    char c;
    int countA=0,countP=0,count=0,countPA=0;
    while((c=getchar())!='\n')
    {
        if(c=='P')
        {
            countP++;//P的个数
        }
        else if(c=='A')
        {
            countPA=countPA+countP;//countPA是PA组合的个数
        }
        else if(c=='T')
        {
            count=(count+countPA)%1000000007;
        }
    }
    printf("%d",count);
    return 0;
}