import math
 
 
class HorseTicket:
 
	def prefixSum(self, races, curpre):
		ret = 0
		race = []
		invalid = False
		for i in curpre:
			for j in curpre:
				if i != j:
					for k in races:
						if i in k and j in k:
							invalid = True
		if invalid:
			return 0
		for u in races:
			valid = True
			for i in u:
				if i in curpre:
					valid = False
			if valid:
				race.append(u)
		races = race
		nn = len(races)
		c = [0 for i in range(nn + 1)]
		c[0] = 1
		for i in range(nn):
			for j in range(nn, 0, -1):
				c[j] += c[j - 1] * len(race[i])
		for i in range(nn + 1):
			ret += math.factorial(i) * c[i]
		return ret
 
	def getTicket(self, races, index):
		# if not (type(races) is tuple and type(index) is int):
		# 	return 'Error'
		total = self.prefixSum(races, '')
		if index >= total:
			return '!'
 
		chars = []
		for u in races:
			chars.extend([i for i in u])
		chars = sorted(list(set(chars)))
 
		ans = ''
		while index > 0:
			index -= 1
			for i in chars:
				if i in ans:
					continue
				prefix = ans + i
				tot = self.prefixSum(races, prefix)
				if tot > index:
					ans = prefix
					break
				else:
					index -= tot
		return ans
 
# print((() + () + tuple([233]) + () + tuple([666]))[1])
# print(type([2333, 4444, 2333]))
print(HorseTicket().getTicket(("B", "A"), 4))
print(HorseTicket().getTicket(("B", "A"), 6))
print(HorseTicket().getTicket(("ace", "bhg", "fdz"), 47))
print(HorseTicket().getTicket(("Top", "C0Der", "1s", "fun"), 673))
print(HorseTicket().getTicket(("q", "w", "e", "r", "t", "y", "u", "i", "o", "p", "a", "s", "d", "f", "g", "h", "j", "k",
							   "l", "z", "x", "c", "v", "b", "n", "m"), 1000000000000000))