"QAQ" is a word to denote an expression of crying. Imagine "Q" as eyes with tears and "A" as a mouth.

Now Diamond has given Bort a string consisting of only uppercase English letters of length n. There is a great number of "QAQ" in the string (Diamond is so cute!). $8$ illustration by 猫屋 https://twitter.com/nekoyaliu 

Bort wants to know how many subsequences "QAQ" are in the string Diamond has given. Note that the letters "QAQ" don't have to be consecutive, but the order of letters should be exact.


-----Input-----

The only line contains a string of length n (1 ≤ n ≤ 100). It's guaranteed that the string only contains uppercase English letters.


-----Output-----

Print a single integer — the number of subsequences "QAQ" in the string.


-----Examples-----
Input
QAQAQYSYIOIWIN

Output
4

Input
QAQQQZZYNOIWIN

Output
3



-----Note-----

In the first example there are 4 subsequences "QAQ": "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN".

Difficulty: interview

Starter code:

Solutions:
s=input()
ans = 0
for i in range(len(s)):
  if s[i] == 'A':
    ans += s[:i].count('Q') * s[i:].count('Q')
print(ans)

from sys import stdin, stdout
from random import randrange

s = stdin.readline().strip()
n = len(s)
ans = 0

for i in range(n):
    for j in range(i + 1, n):
        for z in range(j + 1, n):
            if s[i] == 'Q' and s[j] == 'A' and s[z] == 'Q':
                ans += 1

stdout.write(str(ans))


a = input()
ans = 0
n=len(a)
for j in range(n-2):
    for i in range(j+1,n-1):
        for t in range(i+1,n):
            if a[j] == 'Q' and a[i] =='A' and a[t] == 'Q':
                ans+=1
print(ans)


s = input()
an = 0
for i in range(len(s)):
    for j in range(i + 1, len(s)):
        for k in range(j + 1, len(s)):
            if s[i] + s[j] + s[k] == 'QAQ':
                an += 1
print(an)


s = str(input())
n = len(s)
cnt = 0
for i in range(0, n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if s[i] == 'Q' and s[j] == 'A' and s[k] == 'Q':
                cnt = cnt + 1
print(cnt)

s = input()
ans = 0
for i in range(len(s)):
    for j in range(i + 1, len(s)):
        if s[i] == 'Q' and s[j] == 'A':
            ans += s[j + 1:].count('Q')
print(ans)


n=input()
i=0
for x in range(len(n)):
    if n[x]=='Q':
        for y in range(x,len(n)):
            if n[y]=='A':
                for z in range(y,len(n)):
                    if n[z]=='Q':
                        i+=1
print(i)


a = input()
s=0
for i in range(len(a)-2):
    for j in range(i+1,len(a)-1):
        for k in range(j+1, len(a)):
            if a[i]+a[j]+a[k]=='QAQ': s+=1
print(s)


x = input()
n = len( x )

ans = 0

for i in range( n ):
    for j in range( i+1, n ):
        for k in range( j+1, n ):
            if x[i] == 'Q' and x[j] == 'A' and x[k] == 'Q':
                ans += 1

print( ans )


x = input()
n = 0
for i in range(len(x)):
    if x[i] == 'Q':
        for j in range(i, len(x)):
            if x[j] == 'A':
                for k in range(j, len(x)):
                    if x[k] == 'Q':
                        n += 1
print(n)

s = input()
n = len(s)
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if s[i] == s[k] == 'Q' and s[j] == 'A':
                ans += 1
print(ans)

# Main maut ko takiya, aur kafan ko chaadar banakar audhta hoon!

s=input()

ans=0

for i in range(len(s)):
	
	if(s[i]=='A'):
		ql=s[:i].count("Q")
		qr=s[i+1:].count("Q")
		
		ans+=ql*qr
		
print(ans)




s = input()
r = ''
for i in s:
	if i in 'QA':
		r += i
while len(r) and r[0] != 'Q':
	r = r[1:]
while len(r) and r[-1] != 'Q':
	r = r[:-1]
res = 0
for i in range(len(r)):
	if r[i] == 'A':
		res += r[:i].count('Q') * r[i + 1:].count('Q')
print(res)

s = input()
res = 0
for i in range(len(s)):
    for j in range(i + 1, len(s)):
        for k in range(j + 1, len(s)):
            if s[i] + s[j] + s[k] == "QAQ":
                res += 1
print(res)

s = list(input())
n = len(s)

ans = 0
for i in range(n - 2):
    if s[i] != 'Q':
        continue
    for j in range(i + 1, n - 1):
        if s[j] != 'A':
            continue
        for k in range(j + 1, n):
            if s[k] != 'Q':
                continue
            ans += 1
print(ans)


# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2017/11/19 21:52

"""

S = input()

N = len(S)
ans = 0
for i in range(N):
    if S[i] != 'Q':
        continue
    for j in range(i+1, N):
        if S[j] != 'A':
            continue
        for k in range(j+1, N):
            if S[k] == 'Q':
                ans += 1

print(ans)

s=input()
n=len(s)
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if s[i]=='Q' and s[j]=='A' and s[k]=='Q':
                ans+=1
print(ans)

s = input()

k = 0
for x in range(0, len(s) - 2):
    for y in range(x + 1, len(s) - 1):
        for z in range(y + 1, len(s)):
            if s[x] == 'Q' and s[y] == 'A' and s[z] == 'Q':
                k += 1

print(k)


k = input('')
answer = 0
for i in range(len(k)):
    if k[i] == 'Q':
        for j in range(i + 1, len(k)):
            if k[j] == 'A':
                for z in range(j + 1, len(k)):
                    if k[z] == 'Q':
                        answer += 1
print(answer)

# IAWT
s = input()
ans = 0
for i in range(len(s)):
    for j in range(i+1, len(s)):
        for k in range(j+1, len(s)):
            if s[i] == 'Q' and s[j] == 'A' and s[k] == 'Q':
                ans += 1

print(ans)


s = input()

a = 0
q = 0
ans = 0

for c in s:
    if c == 'Q':
        ans += a
        q += 1
    if c == 'A':
        a += q

print(ans)


s = input()
count = 0
for i in range(len(s)):
	if s[i] == 'Q':
		for j in range(i + 1, len(s)):
			if s[j] == 'A':
				for k in range(j + 1, len(s)):
					if s[k] == 'Q':
						count += 1
print(count)


#http://codeforces.com/contest/894/problem/0
#solved

array = input()
a = len(array)
o = 0

for i in range(a):
    if array[i] == "Q":
        for j in range(i + 1, a):
            if array[j] == "A":
                for k in range(j + 1, a):
                    if array[k] == "Q":
                        o += 1

print(o)

str1 = input()
ans = 0
for i,char1 in enumerate(str1):
	if char1 == 'A':
		count1 = 0
		count2 = 0
		for j in range(i):
			if (str1[j] == 'Q'):
				count1+= 1
		for j in range(i+1, len(str1)):
			if (str1[j] == 'Q'):
				count2+= 1
		ans += count1*count2
print(ans)

q=input()
a,s=[],[]
for i in range(0,len(q)):
    if q[i]=='Q':
        a.append(i)
    elif q[i]=='A':
        s.append(i)
ans=0
for i in a:
    h=list([x for x in s if x>i])
    for j in h:
        ans+=len(list([y for y in a if y>j]))
print(ans)