Increasing subsequences P96556

Write a program that computes how many strictly increasing subsequences with at least two letters are contained in a given word. For instance, the word arrow (we have written the second r in bold italics to distinguish it) contains the increasing subsequences arw, ar, arw, ar, aow, ao, aw, rw, rw and ow.

Input

Input consists of several cases, each with a word made up of between 1 and 100 lowercase letters.

Output

For every case, print the number of strictly increasing subsequences with at least two letters contained in the word. That number will always be less than 10⁹.