UVa 153 - Permalex

// UVa 153 - Permalex

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		BigInteger[] fact = new BigInteger[31];
		fact[0] = BigInteger.ONE;
		for (int i = 1; i < 31; i++)
			fact[i] = fact[i - 1].multiply(BigInteger.valueOf(i));
		String l = scanner.nextLine();
		while (l.charAt(0) != '#') {
			int[] count = new int[256];
			for (char c = 'a'; c <= 'z'; c++)
				count[c] = 0;
			for (int i = 0; i < l.length(); i++)
				count[l.charAt(i)]++;
			BigInteger b4 = BigInteger.ZERO;
			for (int i = 0; i < l.length(); i++) {
				for (char c = 'a'; c < l.charAt(i); c++)
					if (count[c] > 0) {
						count[c]--;
						BigInteger m = BigInteger.ONE;
						int s = 0;
						for (char d = 'a'; d <= 'z'; d++) {
							if (count[d] > 0) {
								m = m.multiply(fact[count[d]]);
								s += count[d];
							}
						}
						count[c]++;
						b4 = b4.add(fact[s].divide(m));
					}
				count[l.charAt(i)]--;
			}
			b4 = b4.add(BigInteger.ONE);
			String sol = b4.toString();
			while (sol.length() < 10)
				sol = " " + sol;
			System.out.println(sol);
			l = scanner.nextLine();
		}
	}
}