Имеется N кг металлического сплава. Из него изготавливают заготовки массой K кг каждая. После этого из каждой заготовки вытачиваются детали массой M кг каждая (из каждой заготовки вытачивают максимально возможное количество деталей). Если от заготовок после этого что-то остается, то этот материал возвращают к началу производственного цикла и сплавляют с тем, что осталось при изготовлении заготовок. Если того сплава, который получился, достаточно для изготовления хотя бы одной заготовки, то из него снова изготавливают заготовки, из них – детали и т.д.

Напишите программу, которая вычислит, какое количество деталей может быть получено по этой технологии из имеющихся исходно N кг сплава.

В королевстве Флатландия наступили тяжелые времена. В пещерах неподалеку от столицы поселился ужасный Черный Дракон. Каждую ночь он выползал на охоту. Много людей погубил он, много построек уничтожил.

Король Флатландии понял, что дальше так продолжаться не может, и нанял отважного Рыцаря, чтобы тот победил рептилию.

Рыцарь принял предложение Короля и начал готовиться к битве. Сам он участия в битве принимать не желал (не рыцарское это дело –– мечом махать), поэтому решил собрать войско из копейщиков. Но копейщикам надо платить, а у Рыцаря из-за кризиса осталось совсем немного сбережений. Помогите ему определить минимальное число копейщиков, необходимое для победы над Черным Драконом.

У копейщика и у дракона есть два параметра: количество очков здоровья и наносимый противнику урон.

В ходе сражения дракон и отряд копейщиков обмениваются ударами. Первым наносит удар отряд копейщиков. При этом дракон получает урон, равный суммарной силе отряда копейщиков. Если дракон не погибает, то он наносит отряду копейщиков ответный удар. Если урон превосходит количество очков здоровья одного копейщика, то он погибает, а следующей копейщик в отряде получает оставшийся урон. Если от этого урона второй копейщик также погибает, то оставшийся урон переходит к третьему копейщику и так далее. Затем удар наносят оставшиеся в живых в отряде копейщики. Бой заканчивается, когда дракон погибает.

Требуется написать программу, которая определяет минимальное количество копейщиков, которое необходимо нанять Рыцарю, чтобы победить Черного Дракона.

Юная программистка Агнесса недавно узнала на уроке информатики об арифметических выражениях. Она заинтересовалась вопросом, что случится, если из арифметического выражения удалить всё, кроме скобок. Введя запрос в своём любимом поисковике, она выяснила, что математики называют последовательности скобок, которые могли бы встречаться в некотором арифметическом выражении, правильными скобочными последовательностями.

Так, последовательность ()(()) является правильной скобочной последовательностью, потому что она может, например, встречаться в выражении (2+2) : (3–(5–2)+4), а последовательности (() и ())( не являются таковыми. Легко видеть, что существует пять правильных скобочных последовательностей, состоящих ровно из шести скобок (по три скобки каждого типа — открывающих и закрывающих): ((())), (()()), (())(), ()(()) и ()()().

Агнесса заинтересовалась простейшими преобразованиями правильных скобочных последовательностей. Для начала Агнесса решила ограничиться добавлением скобок в последовательность. Она очень быстро выяснила, что после добавления одной скобки последовательность перестаёт быть правильной, а вот добавление двух скобок иногда сохраняет свойство правильности. Например, при добавлении двух скобок в различные места последовательности ()() можно получить последовательности (()()), (())(), ()(()) и ()()(). Легко видеть, что при любом способе добавления двух скобок с сохранением свойства правильности одна из новых скобок должна быть открывающей, а другая — закрывающей.

Агнесса хочет подсчитать количество различных способов добавления двух скобок в заданную правильную скобочную последовательность так, чтобы снова получилась правильная скобочная последовательность. К сожалению, выяснилось, что это количество может быть в некоторых случаях очень большим. Агнесса различает способы получения последовательности по позициям добавленных скобок в полученной последовательности. Например, даже при добавлении скобок в простейшую последовательность () можно получить другую правильную скобочную последовательность семью способами: ()(), (()), (()), (()), (()), ()(), ()(). Здесь добавленные скобки выделены жирным шрифтом.

Таким образом, если в полученной последовательности добавленная открывающая скобка стоит в позиции \(i\), а добавленная закрывающая — в позиции \(j\), то два способа, соответствующие парам \((i_1, j_1)\) и \((i_2, j_2)\), считаются различными, если \(i_1\neq i_2\) или \(j_1\neq j_2\).

Требуется написать программу, которая по заданной правильной скобочной последовательности определяет количество различных описанных выше способов добавления двух скобок.