Широкое распространение в стандартных библиотеках многих языков программирования получила реализация сбалансированных деревьев на основе так называемых красно-черных деревьев. В данной задаче вам предлагается посчитать количество красно-черных деревьев заданной формы.

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

Если вершина Y – ребенок вершины X, то говорят, что вершина X является родителем вершины Y. У каждой вершины дерева, кроме одной, есть ровно один родитель. Единственная вершина, не имеющая родителя, называется корнем дерева.

Соединим каждую вершину, кроме корня, с ее родителем. Заметим, что для каждой вершины существует ровно один путь, ведущий в нее от корня.

Двоичное дерево называется красно-черным, если каждая его вершина раскрашена в красный либо в черный цвет, причем выполняются следующие условия:

1. если вершина красная, то ее родитель – черный;
2. количество черных вершин на пути от корня до любой вершины, у которой отсутствует хотя бы один ребенок, одно и то же.

Примеры двоичного дерева, вершины которого раскрашены в два цвета, приведены на следующем рисунке.

Если считать закрашенные вершины черными, а незакрашенные – красными, то дерево на рисунке (а) является красно-черным деревом, а деревья на рисунках (б) и (в) – нет. Для дерева на рисунке (б) нарушается первое свойство – у красной вершины 5 родитель 2 также красный, а в дереве на рисунке (в) нарушается второе свойство – на пути от корня до вершины 1 одна черная вершина, а, например, на пути от корня до вершины 3 – две.

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

Ребята во дворе решили поиграть в прятки. Чтобы выбрать ведущего, который будет искать, они решили воспользоваться считалкой. Считалка состоит из k слов и используется следующим образом.

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

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

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

Помогите им ответить на этот вопрос.

Известно, что сложение и умножение являются ассоциативными операциями. Это значит, что значение выражений вида \(a_1\) + \(a_2\) +...+ \(a_n\) и \(a_1\) . \(a_2\) . ... . \(a_n\) не зависит от порядка выполнения в них действий и, следовательно, не меняется при произвольной расстановке в этих выражениях скобок.

В отличие от сложения и умножения, деление – операция не ассоциативная. Так, значение выражения вида \(a_1\)/\(a_2\)/ ... /\(a_n\) может меняться при расстановке в нем скобок.

Рассмотрим выражение вида

\(p_1\)/\(p_2\)/ ... /\(p_n\),

где все \(p_i\) – простые числа (не обязательно различные). Найдите количество возможных значений, которые может принять указанное выражение после расстановки в нем скобок, а также количество целых чисел среди этих значений. Например, выражение 3/2/2 после расстановки скобок может принять два значения: 3/4 = (3/2)/2 и 3 = 3/(2/2).

Ваня и Петя играют в следующую игру. Ваня пишет на бумаге какую-либо перестановку чисел от 1 до \(N\) (то есть выписывает все числа от 1 до \(N\) в некотором порядке) и расставляет на столе в ряд \(N\) предметов. После этого Петя переставляет предметы в соответствии с Ваниной перестановкой. А именно, Петя выполняет следующие действия: если i-ое число в Ваниной перестановке равно \(a_i\), то Петя ставит предмет, который стоит на i-ом месте, на место с номером \(a_i\).

Обозначим предметы числами от 1 до \(N\). Тогда начальное расположение предметов можно обозначить последовательностью чисел (1, 2, ..., \(N\)). К примеру, если \(N\) = 5, то начальное расположение предметов есть (1, 2, 3, 4, 5). Пусть Ваня написал перестановку <2, 5, 4, 3, 1>. Это значит, что после перемещения предметов они окажутся расставлены в следующем порядке: (5, 1, 4, 3, 2).

Однако, переставив предметы, Петя не останавливается на достигнутом и вновь переставляет их в соответствии с Ваниной перестановкой. Снова, если i-ое число в Ваниной перестановке равно \(a_i\), то Петя ставит предмет, который стоит на i-ом месте на место с номером \(a_i\). Так, если в приведенном выше примере повторно применить перестановку, предметы окажутся расположены в следующем порядке: (2, 5, 3, 4, 1).

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

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