| Codeforces Round 447 (Div. 2) |
|---|
| Закончено |
«QAQ» — смайлик, используемый для выражения плача. Представьте, что «Q» — это глаза со слезами, а «A» — рот.
Алмаз дал Борту строку, состоящую только из заглавных букв латинского алфавита длины n. В строке содержится большое число «QAQ» (Алмаз так мил!).
Борт хочет узнать, сколько подпоследовательностей «QAQ» встречаются в строке, которую дал Алмаз. Обратите внимание, буквы «QAQ» не обязательно должны идти непосредственно друг за другом, но порядок букв должен быть соблюден.
Единственная строка содержит строку длины n (1 ≤ n ≤ 100). Гарантируется, что эта строка содержит только заглавные буквы латинского алфавита.
Выведите одно целое число — количество подпоследовательностей «QAQ» в строке.
QAQAQYSYIOIWIN
4
QAQQQZZYNOIWIN
3
В первом примере 4 подпоследовательностей «QAQ»: «QAQAQYSYIOIWIN», «QAQAQYSYIOIWIN», «QAQAQYSYIOIWIN», «QAQAQYSYIOIWIN».
