Lexicographic Rank of a String

Given a string \(s\), determine its lexicographic rank among all its permutations. The lexicographic rank is defined as 1 plus the number of permutations of \(s\) that are lexicographically smaller than \(s\). It is computed using the formula:

$$\text{rank}(s) = 1 + \sum_{i=0}^{n-1} \Bigl(\text{count}(s[i]) \times \frac{n!}{(n-i)!}\Bigr),$$

where \(\text{count}(s[i])\) is the number of characters to the right of index \(i\) that are smaller than \(s[i]\) and \(n\) is the length of \(s\). The input terminates when a line containing only a single period (.) is encountered. For each valid string, output its lexicographic rank on a new line.

inputFormat

The input is read from standard input (stdin). Each line contains a non-empty string consisting of lowercase alphabets. The input terminates when a line with a single period (.) is encountered.

outputFormat

For each string (excluding the terminating period), output its lexicographic rank on a separate line to the standard output (stdout).## sample

string
abc
bac
.

598
1
3