UVA 153

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

ll fact(string &s) {
    ll ret = 1;
    ll freq[26] = {};
    ll cnt = 0;
    for(char c : s) {
        ret *= ++cnt;
        ret /= ++freq[c-'a'];
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    while(true) {
        string tgt;
        cin >> tgt;
        if(tgt == "#")
            break;
        string s = tgt;
        sort(s.begin(),s.end());
        ll ans = 1;
        for(int i = 0; i < s.length(); i++) {
            while(s[i] != tgt[i]) {
                //cout << "original s is " << s << "\n";
                string f = s.substr(i+1);
                ans += fact(f);
                string newf = "";
                bool changed = false;
                for(int j = 0; j < f.length(); j++) {
                    if(f[j] > s[i]) {
                        if(changed) {
                            newf += f[j];
                        }
                        else {
                            changed = true;
                            newf += s[i];
                            s[i] = f[j];

                        }
                    }
                    else {
                        newf += f[j];
                    }
                }
                for(int j = i+1; j < s.length(); j++) {
                    s[j] = newf[j-i-1];
                }
                //cout << "s is now " << s << "\n";
                //cout << "ans is now " << ans << "\n";
                //return 0;
            }
        }
        string sans = to_string(ans);
        for(int i = 0; i < 10-sans.length(); i++) {
            cout << " ";
        }
        cout << sans << "\n";
    }

    return 0;
}