QAQ
题号:NC23834
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述


给定一个只包含大写字母的长度为的字符串,求中不含相邻字符且长度为的"QAQ"子序列个数。
即:
设字符串的第个字符为,求满足下列条件的三元组个数。



'Q','A','Q'

输入描述:

输入仅一行一个字符串,字符串的长度满足
不会在输入中给出。
保证中只包含大写字母。

输出描述:

输出一行一个整数--满足条件的三元组个数。
示例1

输入

复制
QQAQQ

输出

复制
1

说明

满足条件的三元组只有一个:\ <1,3,5>
示例2

输入

复制
QAQAQ

输出

复制
0
示例3

输入

复制
QQHAHAQQAQ

输出

复制
10