Given a string composed exclusively of 'P', 'A', and 'T' characters, determine the total number of contiguous 'PAT' substrings. Each 'PAT' substring consists of a 'P' flolowed by an 'A' followed by a 'T', with characters in sequence but not necessarily adjacent. The result must be modulo 1000000007 due to potential size.

Input Specification:

The input consists of a single string with length ≤ 10⁵.

Output Specification:

Output the count modulo 1000000007.

Example:

Input: "APPAPT"
Output: 2

Approach:

The solution employs dynamic tracking of partial patterns:

• Iterate through each characetr in the string.
• For each 'P', increment the p_count.
• For each 'A', add the current p_count to pa_count (representing valid 'PA' pairs).
• For each 'T', add the current pa_count to pat_count (representing complete 'PAT' sequences). All additions apply modulo 1000000007 during intermediate steps.

Implementation:

#include <stdio.h>
#define MOD 1000000007

int main() {
    char s[100010];
    while (scanf("%s", s) != EOF) {
        long long p_count = 0, pa_count = 0, pat_count = 0;
        for (int idx = 0; s[idx]; ++idx) {
            if (s[idx] == 'P') ++p_count;
            else if (s[idx] == 'A') pa_count = (pa_count + p_count) % MOD;
            else if (s[idx] == 'T') pat_count = (pat_count + pa_count) % MOD;
        }
        printf("%lld\n", pat_count);
    }
    return 0;
}

Explnaation:

• p_count accumulates the number of 'P' characters encountered.
• pa_count aggregates the count of 'PA' pairs by summing p_count at each 'A' occurrence.
• pat_count tallies the total 'PAT' sequences by accumulating pa_count at each 'T'. Modulo operations ensure intermediate values remain manageable.