Entropy | cho.sh

Problem

In 1948, Claude E. Shannon, in The Mathematical Theory of Communication, introduced his famous formula for the entropy of a discrete set of probabilities $p_1, \ldots, p_n$ :

$H = -\sum_{i} p_i \log_2 p_i.$

We apply this formula to a text string by letting $p_i$ be the relative frequency of occurrence of each distinct character in the string. For example, the string Northeastern European Regional Contest, whose length is 38 (including 3 spaces), has entropy $3.883$ when rounded to 3 digits after the decimal point. The table below lists the relative frequency $p_i$ and the corresponding entropy term $-p_i \log_2 p_i$ for each distinct character of this string.

char	occurs	$p_i$	$-p_i \log_2 p_i$	char	occurs	$p_i$	$-p_i \log_2 p_i$
space	3	$0.079$	$0.289$	i	1	$0.026$	$0.138$
C	1	$0.026$	$0.138$	l	1	$0.026$	$0.138$
E	1	$0.026$	$0.138$	n	4	$0.105$	$0.342$
N	1	$0.026$	$0.138$	o	4	$0.105$	$0.342$
R	1	$0.026$	$0.138$	p	1	$0.026$	$0.138$
a	3	$0.079$	$0.289$	r	3	$0.079$	$0.289$
e	5	$0.132$	$0.385$	s	2	$0.053$	$0.224$
g	1	$0.026$	$0.138$	t	4	$0.105$	$0.342$
h	1	$0.026$	$0.138$	u	1	$0.026$	$0.138$

Given a string, compute its entropy.

Input

The input consists of a single line containing a string of at least 1 and at most 1000 characters. Every character is one of 0–9, a–z, A–Z, . (dot), or a space. Leading, internal, and trailing spaces are all part of the string.

Output

Print a single line containing the entropy $H = -\sum_{i} p_i \log_2 p_i$ of the input string, where $p_i$ is the relative frequency of each distinct character. Round the answer to exactly 3 digits after the decimal point.