There is a string with length *n* ≤ 10^{4}.

Let us denote *f*_{i} as number of occurrences of the *i*'th unique sub sequence.

We need to calculate . Sub sequence does not have to be consective.

I have no idea about the solution so far. So any help would be appreciated.

Here is the source of the problem : link

How to count amount of different subsequences of a string?..

Hint: For each distinct sub sequence count it when its lexicographically minimal by index values.

Some magic: http://www.everfall.com/paste/id.php?tuo8fxsbhlx0.

The main idea is that desired sum may be obtained in the following way: let's iterate over all pairs of subsequences in the string

`S`

and do`ans += 1`

iff they are equal.