When Sasha was studying in the seventh grade, he started listening to music a lot. In order to evaluate which songs he likes more, he introduced the notion of the song's prettiness. The title of the song is a word consisting of uppercase Latin letters. The prettiness of the song is the prettiness of its title.

Let's define the simple prettiness of a word as the ratio of the number of vowels in the word to the number of all letters in the word.

Let's define the prettiness of a word as the sum of simple prettiness of all the substrings of the word.

More formally, let's define the function vowel(c) which is equal to 1, if c is a vowel, and to 0 otherwise. Let s_{i} be the i-th character of string s, and s_{i}..j be the substring of word s, staring at the i-th character and ending at the j-th character (s_{is}_{i} + 1... s_{j}, i ≤ j).

Then the simple prettiness of s is defined by the formula:$\operatorname{simple}(s) = \frac{\sum_{i = 1}^{|s|} \operatorname{vowel}(s_{i})}{|s|}$

The prettiness of s equals $\sum_{1 \leq i \leq j \leq|s|} \operatorname{simple}(s_{i . . j})$

Find the prettiness of the given song title.

We assume that the vowels are I, E, A, O, U, Y.


-----Input-----

The input contains a single string s (1 ≤ |s| ≤ 5·10^5) — the title of the song.


-----Output-----

Print the prettiness of the song with the absolute or relative error of at most 10^{ - 6}.


-----Examples-----
Input
IEAIAIO

Output
28.0000000

Input
BYOB

Output
5.8333333

Input
YISVOWEL

Output
17.0500000



-----Note-----

In the first sample all letters are vowels. The simple prettiness of each substring is 1. The word of length 7 has 28 substrings. So, the prettiness of the song equals to 28.

Difficulty: interview

Starter code:

Solutions:
arr = []
for i in input():
    arr.append(i)
n = len(arr)
res = 0
add = [0] * (n + 10)
add[n] = 1 / n
for i in range(n - 1, 0, -1):
    add[i] = add[i + 1] + 1 / i
for i in range(n):
    if arr[i] in ['I', 'E', 'A', 'O', 'U', 'Y']:
        x = min(i, n - i - 1)
        y = max(i, n - i - 1)
        res += x + 1
        res += (x + 1) * (add[x + 2] - add[y + 1])
        res += (n + 1) * add[y + 1] - (n - y)
print(res)

"""
Codeforces Contest 289 Div 2 Problem E

Author  : chaotic_iak
Language: Python 3.4.2
"""

################################################### SOLUTION

def main():
    s = read(0)
    m = [1 if i in "AEIOUY" else 0 for i in s]
    n = len(m)
    m1 = [0]
    m2 = [0]
    for i in range(n):
        m1.append(m1[-1] + 1/(1+i))
        m2.append(m2[-1] + 1/(n-i))
    mlast = m1[-1]
    for i in range(1,n+1):
        m1[i] = m1[i-1]+m1[i]
        m2[i] = m2[i-1]+m2[i]
    sm = 0
    for i in range(n):
        sm += m[i] * ((i+1)*mlast - m1[i] - m2[i])
    print(sm)

#################################################### HELPERS



def read(mode=2):
    # 0: String
    # 1: List of strings
    # 2: List of integers
    inputs = input().strip()
    if mode == 0: return inputs
    if mode == 1: return inputs.split()
    if mode == 2: return list(map(int, inputs.split()))

def write(s="\n"):
    if s is None: s = ""
    if isinstance(s, list): s = " ".join(map(str, s))
    s = str(s)
    print(s, end="")

write(main())

string = input().strip()
s = [0]
for c in string:
    s.append(s[-1] + (c in 'IEAOUY'))
result, cur = 0, 0
for l in range(1, len(string) + 1):
    cur += s[-l] - s[l - 1]
    result += cur / l
print(result)


song = input()
le = len(song)
su = 0
for x in range(1,le+1):
    su += 1/x
l = [0]*le
l[0] = su
diff = su
for x in range(1,int((le+1)/2)):
    diff -= (1/x + 1/(le+1-x))
    l[x] = l[x-1] + diff
for x in range(int((le+1)/2),le):
    l[x] = l[le-1-x]


ans = 0
for x in range(le):
    let = song[x]
    if let in ['A','E','I','O','U','Y']:
        ans += l[x]

print(ans)


def main():
    s = input()
    n = len(s)
    b = [1.0 / (i + 1) for i in range(n)]
    d = [(n - i) / (i + 1) for i in range(n)]
    d = d[::-1]
    for i in range(1, n):
        b[i] += b[i - 1]
        d[i] += d[i - 1]
    res = 0.0
    for i in range(n):
        if not(s[i] == 'I' or s[i] == 'E' or s[i] == 'A' or s[i] == 'O' or s[i] == 'U' or s[i] == 'Y'):
            continue
        z = [i + 1, n - i]
        z.sort()
        res += z[0] * (b[z[1] - 2] - b[z[0] - 1] + 1) + d[z[0] - 1]
    if len(s) == 1 and res > 0:
        res -= 1
    print(res)
main()


i = input()
l = len(i)
run = [0]*(l+1)
for a in range(1, l+1):
    if i[a-1] in ['A', 'E', 'I', 'O', 'U', 'Y']:
        run[a] = run[a-1] + 1
    else:
        run[a] = run[a-1]
tot = 0

fore = 0
for i in range(1, l+1):
    fore -= 1/i

ey = [fore] + [0] * (l)
for i in range(1, l+1):
    ey[i] = ey[i-1] + 1 / (l+1-i)+1/i

for i in range(1, l+1):
    tot += ey[i] * run[i]
print(tot)
##god = {}
##god2 = {}
##for i in range(0, 15):
##    god[i] = []
##    god2[i] = []
##for i in range(1, l+1):
##    for j in range(i, l+1):
##        god[j].append("1/"+str(j-i+1))
##        god[i-1].append("-1/"+str(j-i+1))
##        god2[j].append(1/(j-i+1))
##        god2[i-1].append(-1/(j-i+1))
##        tot += (run[j]-run[i-1])/(j-i+1)
##print(tot)


from math import fsum


def main():
    l, x = [0, 0], 0
    for c in input():
        if c in ('I', 'E', 'A', 'O', 'U', 'Y'):
            x += 1
        l.append(x)
    n = l[-1]
    res = [float(n)]
    for m in range(2, len(l) - 1):
        n += l[-m] - l[m]
        res.append(n / m)
    print('{:.7f}'.format(fsum(res)))


def __starting_point():
    main()

__starting_point()

ss = list(map(lambda c: c in "IEAOUY", input()))

n = len(ss)
w = [0] * n

for i in range(1, n+1):
    w[0] += 1 / i
w[n-1] = w[0]

sigma = w[0]

for i in range(1, (n - 1) // 2 + 1):
    sigma -= 1 / i + 1 / (n + 1 - i)
    w[n-i-1] = w[i] = w[i-1] + sigma

ans = 0
for i in range(0, n):
    ans += ss[i] * w[i]
    
print(ans)

s = input()
lst=[0]
for i in range(1,len(s)+1):
    lst.append(lst[-1]+1/i)
x=lst[len(s)]
res=0
for i,j in enumerate(s):
    if j in 'AEIOUY':
        res+=x
    x+=lst[len(s)-i-1]-lst[i+1]
print(res)

lst = [0] + [_ in "IEAOUY" for _ in input()]
n = len(lst) - 1
for _ in range(1, n + 1):
    lst[_] += lst[_ - 1]
ans = 0
s = 0
for l in range(1, n // 2 + 1):
    s += lst[n - l + 1] - lst[l - 1]
    ans += s / l + s / (n - l + 1)
if n % 2:
    s += lst[n // 2 + 1] - lst[n // 2]
    ans += s / (n // 2 + 1)
print('%0.9f' % ans)

__author__ = 'PrimuS'

s = input()
n = len(s)

a = [0] * n
ps = [0] * n

for i in range(n):
    if s[i] in "IEAOUY":
        a[i] = 1

ps[0] = a[0]
for i in range(1, n):
    ps[i] = ps[i-1] + a[i]

import math
up = math.ceil((n - 1) / 2)
ss = [0] * up
prev = 0
for i in range(up):
    ss[i] = (a[i] + a[n - i-1]) * (i + 1)
    if i == n - i - 1:
        ss[i] /= 2
    ss[i] += prev
    prev = ss[i]


res = 0
x = 0
res = ps[n-1]
for i in range(2, n):
    k = n - i + 1
    cur = 0
    if k < i:
        cur += (ps[n - k] - ps[k-2]) * k
        cur += ss[k-2]
    else:
        cur += (ps[n - i] - ps[i-2]) * i
        cur += ss[i-2]

    res += cur / i

if n > 1:
    res += ps[n-1] / n

print(res)

from itertools import accumulate
vowels = set('AIUEOY')
s = input()
n = len(s)
vs = list(accumulate(0 if i == 0 else 1 / i for i in range(n + 1)))
r = 0
v = 0
for i in range(n):
    v += vs[n - i] - vs[i]
    if s[i] in vowels:
        r += v
print(r)

from itertools import accumulate
vowels = set('AIUEOY')
s = input()
n = len(s)
vs = list(accumulate(0 if i == 0 else 1 / i for i in range(n + 1)))
r = 0
v = 0
for i in range(n):
    v += vs[n - i] - vs[i]
    if s[i] in vowels:
        r += v
print(r)

word = input()
n = len(word)
def vowel(x):
    if x in ["A","E","I","O","U","Y"]:
        return 1
    else:
        return 0
sums = [0]*n
sums[n-1] = 1/n
for k in range(n-2,-1,-1):
    sums[k] = sums[k+1]+(1/(k+1))
def numb(k):
    if k <= (n+1)//2:
        return (k+1)*(sums[k+1]-sums[n-k-1]) + (n+1)*sums[n-k-1]
    else:
        return numb(n-k-1)
res = 0
if n == 1:
    res = vowel(word[0])
elif n == 2:
    res = (vowel(word[0])+vowel(word[1]))*3/2
elif n == 3:
    res = (vowel(word[0])+vowel(word[2]))*(1+1/2+1/3) + 7/3*vowel(word[1])
else:
    for k in range(n):
        res += vowel(word[k])*numb(k)
print("%.7f" % res)


m, t = 0, [q in 'IEAOUY' for q in input()]
d = s = sum(t)
for k in range(len(t), 0, -1):
    m += d / k
    s -= t[k - 1] + t[-k]
    d += s
print(m)

m, t = 0, [q in 'IEAOUY' for q in input()]
d = s = sum(t)
for k in range(len(t), 0, -1):
    m += d / k
    s -= t[k - 1] + t[-k]
    d += s
print(m)


m, t = 0, [q in 'IEAOUY' for q in input()]
d = s = sum(t)
for k in range(len(t), 0, -1):
    m += d / k
    s -= t[k - 1] + t[-k]
    d += s
print(m)


m, t = 0, [q in 'IEAOUY' for q in input()]
d = s = sum(t)
for k in range(len(t), 0, -1):
    m += d / k
    s -= t[k - 1] + t[-k]
    d += s
print(m)


m, t = 0, [q in 'IEAOUY' for q in input()]
d = s = sum(t)
for k in range(len(t), 0, -1):
    m += d / k
    s -= t[k - 1] + t[-k]
    d += s
print(m)


m, t = 0, [q in 'IEAOUY' for q in input()]
d = s = sum(t)
for k in range(len(t), 0, -1):
    m += d / k
    s -= t[k - 1] + t[-k]
    d += s
print(m)


m, t = 0, [q in 'IEAOUY' for q in input()]
d = s = sum(t)
for k in range(len(t), 0, -1):
    m += d / k
    s -= t[k - 1] + t[-k]
    d += s
print(m)


m, t = 0, [q in 'IEAOUY' for q in input()]
d = s = sum(t)
for k in range(len(t), 0, -1):
    m += d / k
    s -= t[k - 1] + t[-k]
    d += s
print(m)


m, t = 0, [q in 'IEAOUY' for q in input()]
d = s = sum(t)
for k in range(len(t), 0, -1):
    m += d / k
    s -= t[k - 1] + t[-k]
    d += s
print(m)


def sum_vowels(s, i, j):
	ans = 0

	for index in range(i, j + 1):
		if s[index] in "AEIOUY":
			ans += 1

	return ans

def __starting_point():
	s = input()
	n = len(s)

	ans = 0

	num = 0
	den_inv = 0
	prev_sum = sum_vowels(s, 0, n - 1)
	for i in range(int(n / 2)):
		num += prev_sum
		den_inv = 1 / (i + 1) + 1 / (n - i)

		ans += num * den_inv

		if s[i] in "AEIOUY": prev_sum -= 1
		if s[n - 1 - i] in "AEIOUY": prev_sum -= 1

	if (n % 2 == 1):
		i = int(n / 2)
		num += sum_vowels(s, i, i)
		den_inv = 1 / (i + 1)

		ans += num * den_inv

	print("{:.6f}".format(ans))
__starting_point()