애너그램 (Anagram)

어떤 문자열의 문자 순서를 바꾸어 다른 문자열을 만드는 것, 그리고 그렇게 순서를 바꾸어 만든 문자열을 애너그램(Anagram)이라고 한다. 이 문제에서는 순서를 한 번도 바꾸지 않은 문자열도 원래 문자열의 애너그램이라고 하자. 즉 문자열 "EARTH"는 문자열 "HEART"의 애너그램이고, 문자열 "HEART"도 문자열 "HEART"의 애너그램이다.

문자열이 주어지면, 대부분의 경우 그 문자열의 애너그램은 여러 가지가 있을 수 있다. 예를 들어 문자열 "IOI"의 애너그램은 자기 자신을 포함하여 사전순으로 "IIO", "IOI", "OII"의 3가지가 있다.

이제 어떤 문자열이 주어진다. 해야 할 일은 주어진 문자열이 그 문자열의 모든 애너그램 가운데 사전순으로 몇 번째에 나타나는지 알아내는 프로그램을 작성하는 것이다.

예를 들어 문자열 "EARTH"는 "EARTH"의 애너그램 가운데 28번째이고, 문자열 "HEART"는 "HEART"의 애너그램 가운데 55번째이다.

입력은 한 줄뿐이며, 이 줄은 알파벳 대문자로만 이루어진 20자 이하의 문자열이다. 이 문자열에 대해 문제의 계산을 하면 된다.

출력은 표준 출력으로 한다. 입력으로 주어진 문자열이 그 문자열의 애너그램 가운데 사전순으로 몇 번째 문자열인지 정수로 한 줄에 출력한다.

주의 오버플로에 주의해야 한다.

$2^{32} < 20 \times 19 \times \cdots \times 3 \times 2 \times 1 < 2^{64}$

이다.