Таблетки
Тетя Лиззи принимает половину таблетки определенного лекарства каждый день. Она начинает с бутылки, содержащей N таблеток.
В первый день она достает случайную таблетку, разламывает ее на две половины, принимает одну половину и кладет другую обратно в бутылку.
В последующие дни она достает случайный кусочек (это может быть либо целая таблетка, либо половина таблетки) из бутылки. Если это половина таблетки, она принимает ее. Если это целая таблетка, она принимает одну половину и кладет другую обратно в бутылку.
Сколькими способами она может опустошить бутылку? Мы представляем последовательность таблеток, вынутых из бутылки в течение 2N дней, в виде строки, где i-й символ — это W, если в i-й день была выбрана целая таблетка, и H, если была выбрана половина таблетки (0 ≤ i < 2N). Сколько различных допустимых строк существует, которые опустошают бутылку?
Входные данные
Входные данные содержат не более 1000 экземпляров задачи. Для каждого экземпляра задачи будет одна строка ввода: положительное целое число N ≤ 30, количество таблеток, изначально находящихся в бутылке. Конец ввода обозначен 0.
Выходные данные
Для каждого экземпляра задачи выведите одно число на новой строке. Это будет количество различных способов, которыми можно опустошить бутылку.