153 - Permalex

給任意一字串,我們可透過字元換位,而得到新字串,如果我們加上序號(字典次序),則可用唯一的數字來區別不同位置的文字。例如,”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