{"problem":{"name":"C. Проблемы Старосты","description":{"content":"Влад М. недавно окончил лицей и наконец-то поступил в лучший университет на свете — СГАУ! Влад — прирождённый лидер, поэтому одногруппники сразу же выбрали его своим старостой. Большая часть занятий в","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10085C"},"statements":[{"statement_type":"Markdown","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## Входные Данные\n\nВ первой строке входных данных записано единственное целое число n (2 ≤ n ≤ 109) — количество студентов в группе Влада, включая его самого.\n\n## Выходные Данные\n\nВ первой строке выведите количество возможных разбиений на подгруппы. Если количество возможных разбиений на подгруппы больше 106, выведите вместо количества возможных разбиений _TOO HARD_ (в точности так, как записано).\n\n## Примеры\n\nВходные данные3Выходные данные8Входные данные21Выходные данныеTOO HARD\n\n## Примечание\n\nПояснение к первому примеру.Есть 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.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10085C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}