← 返回题目列表

Codeforces · 894/A

A. QAQ表情

中文机器翻译题面 查看原题

“QAQ”是表示哭泣的表情的词。将“Q”想象为含泪的眼睛,将“A”想象为一张嘴。

现在 Diamond 给了 Bort 一个仅由大写英文字母组成、长度为 n 的字符串。字符串中有很多“QAQ”(钻石太可爱了!)。

猫屋插图 https://twitter.com/nekoyaliu

Bort 想知道 Diamond 给出的字符串中有多少个子序列“QAQ”。请注意,字母“QAQ”不必是连续的,但字母的顺序应该准确。

输入

唯一一行包含长度为 n (1 ≤ n ≤ 100) 的字符串。保证字符串只包含大写英文字母。

输出

打印单个整数 - 字符串中子序列“QAQ”的数量。

示例

输入 #1

QAQAQYSYIOIWIN

输出 #1

4

输入 #2

QAQQQZZYNOIWIN

输出 #2

3

注意

在第一个示例中,有 4 个子序列“QAQ”:“QAQAQYSYIOIWIN”、“QAQAQYSYIOIWIN”、“QAQAQYSYIOIWIN”、“QAQAQYSYIOIWIN”。