{"raw_statement":[{"iden":"statement","content":"Влад М. недавно окончил лицей и наконец-то поступил в лучший университет на свете — СГАУ! Влад — прирождённый лидер, поэтому одногруппники сразу же выбрали его своим старостой. Большая часть занятий в СГАУ проходит по подгруппам, и расписание составлено исходя из того, что каждая группа разделена на две подгруппы. Староста должен составить списки подгрупп и отнести их в деканат. Это означает, что Влад должен записать каждого студента в подгруппу #1 или в подгруппу #2. Разумеется, каждый студент должен быть записан ровно в одну подгруппу. Размеры подгрупп могут быть любыми; допустимо, что в одной из подгрупп может не быть ни одного студента.\n\nНекоторые одногруппники уже успели сдружиться, а некоторые, напротив, уже недолюбливают друг друга. Так что на Влада посыпалась куча просьб вида «Я безумно влюблён в XX, поэтому хочу учиться с ней в одной подгруппе», «XY странно смотрит на меня, мне кажется, он сумасшедший, не хочу оказаться в одной подгруппе с ним» и т.д. Конечно, были и пожелания иного рода, например, «Я хочу учиться в подгруппе #1, так как там нет пар в 8 часов утра в понедельник». Но этих просьб и пожеланий было очень, очень много...\n\nПредприняв несколько попыток составить списки подгрупп, Влад осознал, что это не так-то просто сделать. Поэтому он решил написать программу, выбирающую такое разбиение на подгруппы, при котором будет удовлетворено наибольшее количество просьб одногруппников. \n\n«Достаточно просто перебрать все возможные разбиения на подгруппы и посчитать для каждого разбиения, сколько просьб будет выполнено. Плёвое дело!» — рассуждал Влад. Внезапно его посетила мысль, что количество возможных разбиений может быть настолько большим, что программа не сможет проверить их все не только до конца семестра, но и до конца обучения. \n\nЗная, сколько человек учится в группе Влада, помогите ему определить количество возможных разбиений. Если возможных разбиений больше миллиона, скажите ему, что их слишком много. Два разбиения считаются различными, если найдётся хотя бы один студент, который в этих двух разбиениях записан в разные подгруппы.\n\nВ первой строке входных данных записано единственное целое число n (2 ≤ n ≤ 109) — количество студентов в группе Влада, включая его самого.\n\nВ первой строке выведите количество возможных разбиений на подгруппы. \n\nЕсли количество возможных разбиений на подгруппы больше 106, выведите вместо количества возможных разбиений _TOO HARD_ (в точности так, как записано).\n\nПояснение к первому примеру.\n\nЕсть 8 способов разбиения:\n\n1) первая подгруппа — студенты 1, 2 и 3, вторая подгруппа — никого;\n\n2) первая подгруппа — студенты 1 и 2, вторая подгруппа — студент 3;\n\n3) первая подгруппа — студенты 1 и 3, вторая подгруппа — студент 2;\n\n4) первая подгруппа — студент 1, вторая подгруппа — студенты 2 и 3;\n\n5) первая подгруппа — студенты 2 и 3, вторая подгруппа — студент 1;\n\n6) первая подгруппа — студент 2, вторая подгруппа — студенты 1 и 3;\n\n7) первая подгруппа — студент 3, вторая подгруппа — студенты 1 и 2;\n\n8) первая подгруппа — никого, вторая подгруппа — студенты 1, 2 и 3.\n\n"},{"iden":"входные данные","content":"В первой строке входных данных записано единственное целое число n (2 ≤ n ≤ 109) — количество студентов в группе Влада, включая его самого."},{"iden":"выходные данные","content":"В первой строке выведите количество возможных разбиений на подгруппы. Если количество возможных разбиений на подгруппы больше 106, выведите вместо количества возможных разбиений _TOO HARD_ (в точности так, как записано)."},{"iden":"примеры","content":"Входные данные3Выходные данные8Входные данные21Выходные данныеTOO HARD"},{"iden":"примечание","content":"Пояснение к первому примеру.Есть 8 способов разбиения:1) первая подгруппа — студенты 1, 2 и 3, вторая подгруппа — никого;2) первая подгруппа — студенты 1 и 2, вторая подгруппа — студент 3;3) первая подгруппа — студенты 1 и 3, вторая подгруппа — студент 2;4) первая подгруппа — студент 1, вторая подгруппа — студенты 2 и 3;5) первая подгруппа — студенты 2 и 3, вторая подгруппа — студент 1;6) первая подгруппа — студент 2, вторая подгруппа — студенты 1 и 3;7) первая подгруппа — студент 3, вторая подгруппа — студенты 1 и 2;8) первая подгруппа — никого, вторая подгруппа — студенты 1, 2 и 3."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"Let $ n \\in \\mathbb{Z} $ be the number of students, with $ 2 \\leq n \\leq 10^9 $.\n\nEach student is assigned to exactly one of two distinct subgroups (subgroup #1 or subgroup #2).\n\nThe total number of possible assignments is $ 2^n $, since each student has 2 choices.\n\nHowever, the problem considers two assignments different if at least one student is in a different subgroup, and **does not** identify subgroup #1 with subgroup #2 (i.e., label matters).\n\nThus, the number of distinct partitions is $ 2^n $.\n\n**Constraints**\n- $ 2 \\leq n \\leq 10^9 $\n\n**Objective**\nCompute $ 2^n $. If $ 2^n > 10^6 $, output `TOO HARD`; otherwise, output $ 2^n $.","simple_statement":"Given n students, each can be in group 1 or group 2.  \nCount the total number of ways to assign all students to one of the two groups.  \nIf the number is more than 1,000,000, print \"TOO HARD\".  \nOtherwise, print the number.","has_page_source":false}