前缀和思想：

对于字符串中的每一个A，它能够构成字串PA的数量是它之前的所有P的数量。
对于字符串中的每一个T，它能够构成字串PAT的数量是它之前所有字串PA的数量。

$O(n)的时间复杂度$

这道题和14届蓝桥杯CB有道题很相似

s = input()
res = 0

p, pa, pat = 0, 0, 0

for i in range(len(s)):
    if s[i] == 'P':
        p += 1
    elif s[i] == 'A':
        pa += p
    elif s[i] == 'T':
        pat = (pat + pa) % 1000000007

print(pat)

超时三层for循环代码：

s = input()
res = 0

for i in range(len(s)):
    if s[i] != 'P':
        continue

    for j in range(i,len(s)):
        if s[j] != 'A':
            continue

        for k in range(j,len(s)):
            if s[k] != 'T':
                continue

            res = (res + 1) % 1000000007

print(res)