def getMax(level)
	max = 0
	for i in 1..level-1
	   if $st[i] > max
	   	max = $st[i]
	   end	
    end
    return max
end    
 
def init(level)
    $st[level] = 0
end
 
def succ(level)
    if $st[level]<getMax(level)+1
      $st[level]+=1
      return true
    end
    return false
end
 
def valid(level)
  return true
end
def sol(level)
  return $n == level
end
 
def printf()
  $cnt +=1
  print $cnt
  takemax = $st.max()
  for i in 1..takemax
      print "{"
      for j in i..$n
        if $st[j] == i
          print j, ''
        end
      end
      print "}"
  end
  print"\n"
end
 
def bk(level)
    init(level)
    while succ(level)
          if valid(level)
             if sol(level)
               printf()
             else
               bk(level+1)
             end
          end
    end
end
def partitions
  $cnt = 0	
  $n = gets.chomp.to_i
  $st = [0] * ($n+1)
  $st[1] = 1
  bk(2)
end
partitions
 

ZGVmIGdldE1heChsZXZlbCkKCW1heCA9IDAKCWZvciBpIGluIDEuLmxldmVsLTEKCSAgIGlmICRzdFtpXSA+IG1heAoJICAgCW1heCA9ICRzdFtpXQoJICAgZW5kCQogICAgZW5kCiAgICByZXR1cm4gbWF4CmVuZCAgICAKCQpkZWYgaW5pdChsZXZlbCkKICAgICRzdFtsZXZlbF0gPSAwCmVuZAoKZGVmIHN1Y2MobGV2ZWwpCiAgICBpZiAkc3RbbGV2ZWxdPGdldE1heChsZXZlbCkrMQogICAgICAkc3RbbGV2ZWxdKz0xCiAgICAgIHJldHVybiB0cnVlCiAgICBlbmQKICAgIHJldHVybiBmYWxzZQplbmQKCmRlZiB2YWxpZChsZXZlbCkKICByZXR1cm4gdHJ1ZQplbmQKZGVmIHNvbChsZXZlbCkKICByZXR1cm4gJG4gPT0gbGV2ZWwKZW5kCgpkZWYgcHJpbnRmKCkKICAkY250ICs9MQogIHByaW50ICRjbnQKICB0YWtlbWF4ID0gJHN0Lm1heCgpCiAgZm9yIGkgaW4gMS4udGFrZW1heAogICAgICBwcmludCAieyIKICAgICAgZm9yIGogaW4gaS4uJG4KICAgICAgICBpZiAkc3Rbal0gPT0gaQogICAgICAgICAgcHJpbnQgaiwgJycKICAgICAgICBlbmQKICAgICAgZW5kCiAgICAgIHByaW50ICJ9IgogIGVuZAogIHByaW50IlxuIgplbmQKCmRlZiBiayhsZXZlbCkKICAgIGluaXQobGV2ZWwpCiAgICB3aGlsZSBzdWNjKGxldmVsKQogICAgICAgICAgaWYgdmFsaWQobGV2ZWwpCiAgICAgICAgICAgICBpZiBzb2wobGV2ZWwpCiAgICAgICAgICAgICAgIHByaW50ZigpCiAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgIGJrKGxldmVsKzEpCiAgICAgICAgICAgICBlbmQKICAgICAgICAgIGVuZAogICAgZW5kCmVuZApkZWYgcGFydGl0aW9ucwogICRjbnQgPSAwCQogICRuID0gZ2V0cy5jaG9tcC50b19pCiAgJHN0ID0gWzBdICogKCRuKzEpCiAgJHN0WzFdID0gMQogIGJrKDIpCmVuZApwYXJ0aXRpb25zCg==

NQ==

5