給任意一字串，我們可透過字元換位，而得到新字串，如果我們加上序號(字典次序)，則可用唯一的數字來區別不同位置的文字。例如，”acab”可得到12個不同的排列序列：如下圖所示。而acab 是排在第5位置。請寫一個程式可以作這種轉換，但要注意，字串的位置數，可以很大，但不會超過 $2^{31}-1$。
| aabc | 1 |
| aacb | 2 |
| abac | 3 |
| abca | 4 |
| acab | 5 |
| acba | 6 |
| baac | 7 |
| baca | 8 |
| bcaa | 9 |
| caab | 10 |
| caba | 11 |
| cbaa | 12 |
Input
每組測試資料1列，有1個僅包含小寫字元的字串（長度不會超過30），字串”#”代表輸入結束。
Output
每組測試資料輸出一個整數，代表輸入字串在序列中的位置（長度10，靠右對齊，請參考Sample Output）。
Sample Input
acab
bacaa
abc
cba
#
Sample Output
5
15
1