import heapq

ch = 'ACGT'
k = 7

heap = []
heapq.heappush(heap, '')

while len(heap):
  seq = heapq.heappop(heap)
  if len(seq) - k + 1 == len(ch) ** k:
    print seq, len(seq)
    break
  for c in ch:
    n = seq + c
    if len(n) < k or n[-k:] not in seq:
      heapq.heappush(heap, n)