사전순 K번째 애너그램

문자열의 애너그램은 원래 문자열과 같은 문자를 전부 그대로 써서 만든 문자열이다. 원래 문자열도 자기 자신의 애너그램에 포함된다.

예를 들어 ACM의 애너그램은 사전순으로 ACM, AMC, CAM, CMA, MAC, MCA 6개다. ICPC의 애너그램은 사전순으로 CCIP, CCPI, CICP, CIPC, CPCI, CPIC, ICCP, ICPC, IPCC, PCCI, PCIC, PICC 12개다.

문자열과 순위 $K$가 주어지면 사전순으로 $K$번째 애너그램을 구한다.

각 줄에 질의 하나가 원래 단어와 순위 $K$ 순서로, 공백을 사이에 두고 주어진다. 단어는 대문자 A부터 Z까지만 쓰며 길이는 16 이하다. $K$는 1 이상이고 그 단어의 서로 다른 애너그램 개수 이하다. # 0인 줄이 나오면 입력이 끝난다. 이 줄은 질의가 아니다.

가장 큰 경우 $K$가 $16! = 20922789888000$에 이르므로 64비트 정수에 담아야 한다. Java는 long, C++는 long long을 쓰면 된다.

질의마다 그 단어의 사전순 $K$번째 애너그램을 한 줄에 출력한다.