Все знают, что битва при Эндоре — миф, придуманный Джорджем Лукасом ради раскрутки своего фильма. На самом деле никакой битвы при Эндоре не было, и Первая Галактическая Империя существует в полном здравии и по сей день.

В Первой Галактической Империи проживают представители n рас. Дабы доказать их свободу, равенство и братство, Император повелел ввести государственные праздники. На каждый из этих праздников представители одного непустого подмножества рас должны дарить подарки представителям другого непустого подмножества рас, не пересекающегося с первым.

Прислуга Императора не очень сильна в математике, поэтому вам необходимо посчитать, сколько всего бывает различных праздников такого вида. Два праздника считаются различными, если они отличаются множеством рас, которое дарит подарки, или множеством рас, которому дарят подарки.